Penerapan Algoritma Vektor untuk mencocokkan String (String Matching) pada Finite Automata

NATALIANI, Yessica, Drs. Retantyo Wardoyo, MSc.,PhD

2006 | Tesis | S2 Ilmu Komputer

Finite automata merupakan alat yang sangat berguna untuk mengkomputasi suatu string. Permasalahan memperkirakan kecocokan string adalah menemukan semua lokasi di mana suatu pola diperkirakan cocok dengan substring dari suatu teks yang diketahui dengan maksimal perbedaan tertentu. Algoritma yang dipakai untuk penyelesaian permasalahan memperkirakan kecocokan string adalah algoritma vektor bit. Algoritma vektor bit digunakan dengan memanfaatkan keparalelan antara teks dengan pola, karena keparalelan vektor dapat mempercepat proses eksekusi dengan mengurangi proses pengulangan. Permasalahan memperkirakan kecocokan string dapat diimplementasikan pada bidang biologi, yaitu untuk menguji kecocokan DNA.

Finite automata is a very useful device to compute string. An approximate string matching problem is to find the location where a pattern is approximately matched with sub string taken from some text with appointed maximum difference. We use bit vector algorithm to solve approximate string matching problem. Bit vector algorithm is used properly by using parallelism between the text and the pattern, because vector parallelism can take a short time at execution process by reducing iteration. Approximate string matching problem can be implemented in biology when we test the DNA matching.

Kata Kunci : Algoritma Vektor Bit,String Matching,DNA, approximate string matching problem, bit vector algorithm, DNA matching