Algoritma String
Algoritma string memproses urutan simbol — teks, DNA, atau data linier lainnya — untuk menemukan pola, mengindeks teks besar untuk pencarian cepat, dan menyelaraskan urutan berdasarkan kesamaan.
Definition
Algoritma string adalah prosedur dan struktur data yang beroperasi pada string — urutan karakter terbatas yang diambil dari alfabet — untuk memecahkan masalah seperti menemukan pola, pengindeksan untuk pencarian cepat, dan mengukur atau menyelaraskan kesamaan antar urutan.
Scope
Area ini mencakup algoritma dan struktur data yang dikhususkan untuk string: pencocokan pola yang tepat dan perkiraan, struktur indeks (tries, pohon sufiks, dan array sufiks) yang memproses awal teks untuk kueri berulang, dan metode penyelarasan urutan untuk membandingkan string. Ini terhubung dengan pemrograman dinamis (penyelarasan), struktur data (pohon dan array), dan aplikasi dalam biologi komputasi, pengambilan teks, dan pemrosesan bahasa alami.
Sub-topics
Core questions
- Bagaimana pola dapat ditemukan dalam teks lebih cepat daripada perbandingan karakter-per-karakter yang naif?
- Bagaimana teks besar diproses awal sehingga banyak kueri selanjutnya menjadi cepat?
- Bagaimana kesamaan antara dua string didefinisikan dan dihitung?
- Bagaimana ukuran alfabet dan panjang string memengaruhi efisiensi algoritma string?
- Bagaimana metode pencocokan tepat diperluas ke pencocokan perkiraan atau multi-pola?
Key concepts
- alfabet dan string
- pencocokan pola tepat
- Knuth-Morris-Pratt dan Boyer-Moore
- tries
- pohon sufiks dan array sufiks
- jarak edit
- penyelarasan urutan
- pencocokan perkiraan
Key theories
- Pencocokan pola tepat waktu linear
- Dengan memproses awal pola untuk memanfaatkan informasi dari pencocokan parsial, algoritma seperti Knuth-Morris-Pratt dan Boyer-Moore menemukan semua kemunculan pola dalam waktu linear terhadap panjang teks, menghindari biaya kuadrat dari pencocokan naif.
- Struktur indeks untuk teks
- Pohon sufiks dan array sufiks memproses awal teks sehingga kueri pola arbitrer, pengulangan, dan pertanyaan substring umum terpanjang dapat dijawab dengan cepat, menukar biaya konstruksi dengan pencarian berulang yang cepat.
Clinical relevance
Algoritma string adalah dasar untuk pencarian teks dan bioinformatika: pencocokan pola mendukung utilitas pencarian, editor teks, dan deteksi intrusi; struktur sufiks mengindeks mesin pencari dan basis data genom; dan penyelarasan urutan adalah inti untuk membandingkan urutan DNA, RNA, dan protein dalam biologi molekuler.
History
Pencocokan string yang efisien muncul pada tahun 1970-an dengan algoritma Knuth-Morris-Pratt (1977) dan Boyer-Moore (1977). Pohon sufiks (Weiner, 1973; McCreight, 1976; Ukkonen, 1995) dan kemudian array sufiks (Manber dan Myers, 1990) memberikan pengindeksan yang kuat, dan bidang ini berkembang pesat melalui biologi komputasi, yang disurvei dalam teks Gusfield tahun 1997.
Key figures
- Donald Knuth
- James H. Morris
- Vaughan Pratt
- Robert Boyer
- J Strother Moore
- Dan Gusfield
Related topics
Seminal works
- knuth1977
- gusfield1997
- cormen2009
Frequently asked questions
- Mengapa memproses awal pola atau teks daripada mencari secara langsung?
- Pencocokan naif dapat memakan waktu sebanding dengan hasil kali panjang pola dan teks. Pemrosesan awal pola (seperti pada Knuth-Morris-Pratt) memberikan pencarian waktu linear, dan pemrosesan awal teks ke dalam indeks (pohon sufiks atau array) memungkinkan banyak kueri selanjutnya masing-masing berjalan jauh lebih cepat, yang menguntungkan ketika teks yang sama dicari berulang kali.
- Bagaimana algoritma string digunakan dalam biologi?
- DNA, RNA, dan protein secara alami direpresentasikan sebagai string, sehingga pencocokan pola menemukan motif, struktur sufiks mengindeks genom untuk pencarian cepat, dan algoritma penyelarasan urutan mengukur kesamaan antara urutan untuk menyimpulkan hubungan evolusi dan fungsi.