Analiza porównawcza algorytmów wyszukiwania wzorca w tekście

• Autorzy: Widuch J.

Warianty tytułu

EN

A comparative analysis of string searching algorithms

• Języki publikacji: PL

Abstrakty

PL

Jednym z problemów związanych z przetwarzaniem tekstów jest problem wyszukiwania wzorca w tekście, którego celem jest wyznaczenie wszystkich wystąpień w zadanym tekście innego tekstu, zwanego wzorcem. W niniejszej pracy dokonano analizy porównawczej istniejących algorytmów wyszukiwania wzorca w tekście, przy czym kryterium porównawczym jest czas wyszukiwania wzorca. Wyniki przeprowadzonych badań zamieszczono w pracy.

EN

One of the text processing problems is the pattern matching problem. The goal of the problem is to find all places where one text or string, called pattern, is found within the given text. In this paper, a comparative analysis of existing string matching algorithms is presented, and the comparison criterion is the time of searching the pattern in the text. The results of the tests are also presented.

Słowa kluczowe

PL

tekst; wzorzec; alfabet; wyszukiwanie wzorca; prefiks; sufiks; funkcja prefiksowa

EN

text; pattern; alphabet; string searching; prefix; suffix; prefix function

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2013
• Tom: Vol. 34, nr 1
• Strony: 5--29
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

Widuch J.

• Politechnika Śląska, Instytut Informatyki, ul. Akademicka 16, 44–100 Gliwice, Polska

Bibliografia

• 1. Abu–Alhaj M. M., Halaiyqah M., Abu–Hashem M. A., Hnaif A. A., Abouabdalla O., Manasrah A. M.: An innovative platform to improve the performance of exact string matching algorithms. International Journal of Computer Science and Information Security, Vol. 7, No. 1, 2010, s. 280÷283.
• 2. Adjeroh D., Bell T., Mukherjee A.: The Burrows–Wheeler Transform: Data Compression,
• 3. Suffix Arrays, and Pattern Matching. Springer, 2008.
• 4. Atallah M. J.: Algorithms and Theory of Computation Handbook. CRC-Press, 1st edition, 1998.
• 5. Boyer R. S., Moore J. S.: A Fast String Searching Algorithm. Communications of the ACM, Vol. 20, No. 10, 1977, s. 762÷772.
• 6. Charras Ch., Lecroq T.: Handbook of Exact String Matching Algorithms. College Publications, 2004.
• 7. Cormen T. H., Leiserson Ch. E., Rivest R. L.: Wprowadzenie do algorytmów. WNT, Warszawa 2000.
• 8. Crochemore M., Rytter W.: Jewels of Stringology. World Scientific Pub Co Inc, 1st edition, 2002.
• 9. Gusfield D.: Algorithm on strings, trees, and sequences. Cambridge University Press, 1997.
• 10. Hancart C.: Une analyse en moyenne de l'algorithme de Morris et Pratt et de ses raffinements. Théorie des Automates et Applications, Actes des 2e Journées Franco–Belges, D. Krob ed., Rouen, France, 1992, s. 99÷110.
• 11. Hancart C.: Analyse exacte et en moyenne d'algorithmes de recherche d'un motif dans un texte, Thése de doctorat de l'Université de Paris , France, 1993.
• 12. Horspool R. N.: Practical fast searching in strings. Software – Practice and Experience, Vol. 10, No. 6, 1980, s. 501÷506.
• 13. Karp R. M., Rabin M. O.: Efficient randomized pattern–matching algorithms. Technical Report TR–31–81 , Aiken Computation Laboratory, Harvard University, 1981.
• 14. Knuth D., Morris Jr. J. H., Pratt V.: Fast pattern matching in strings. SIAM Journal on Computing, Vol. 6, No. 2, 1977, s. 323÷350.
• 15. Manber U., Myers E.W.: Suffix Arrays: A New Method for On-Line String Searches. SIAM Journal of Computing, Vol. 22, No. 5, 1993, s. 935÷948.
• 16. Raita T.: Tuning the Boyer–Moore–Horspool string searching algorithm. Software – Practice & Experience, Vol. 22, No. 10, 1992, s. 879÷884.
• 17. Smith s. D.: Experiments with a very fast substring search algorithm. Software – Practice and Experience, Vol. 21, No. 10, 1991, s. 1065÷1074.
• 18. Sunday D. M.: A very fast substring search algorithm. Communications of the ACM, Vol. 33, No. 8, s. 132÷142, 1990.