ZASTOSOWANIE ALGORYTMU WYSZUKIWANIA WIELU WZORCÓW OPARTEGO O TECHNIKĘ Q-GRAMÓW DO WYSZUKIWANIA PRZYBLIŻONEGO
Abstrakt
Rozważamy zastosowanie algorytmu wyszukiwania wielu wzorców (Multi AOSO on q-Grams) do wyszukiwania przybliżonego. Proponujemy rozwiązanie on-line, upraszczające problem wyszukiwania przybliżonego do wyszukiwania wielu wzorców. Zaprezentowane rozwiązanie umożliwia relatywnie szybko wyszukiwać wiele wzorców dla odległości Levenshteina (lub Hamminga) z ograniczeniem do k. W artykule porównane jest rozwiązanie oparte na algorytmie MAG oraz [4]. Badania eksperymentalne przeprowadzone na zbiorach DNA, English, Proteins and XML z różnymi wartościami k wykazały, że zaproponowany algorytm osiąga relatywnie dobre wyniki w praktycznym zastosowaniu.
Słowa kluczowe:
przetwarzanie tekstu, wyszukiwanie przybliżone, algorytmy tekstowe, q-gramBibliografia
Baeza-Yates R.A., Navarro G.: New and faster filters for multiple approximate string matching. Random Structures and Algorithms 20(1), 2011, 23–49.
Google Scholar
Baeza-Yates R., Navarro G.: New and Faster Filters for Multiple Approximate String Matching. Random Structures and Algorithms 20/2002, 23–49.
Google Scholar
Burkhardt S., Kärkkäinen J.: Better filtering with gapped q-grams. Fundam. Inform. 56(1-2)/2003, 51–70.
Google Scholar
Fredriksson K., Navarro G.: Average-optimal single and multiple approximate string matching. ACM J. Exp. Alg. 9(1.4)/2004, 1–47.
Google Scholar
Fredriksson K.: Shift–or string matching with super-alphabets. Information Processing Letters 87(1)/2003, 201–204.
Google Scholar
Grossi R., Luccio F.: Simple and efficient string matching with k mismatches. Information Processing Letters 33(3)/1989, 113–120.
Google Scholar
Jokinen P., Ukkonen E.: Two algorithms for approximate string matching in static texts. Proc. MFCS 16/1991, 240–248.
Google Scholar
Landau G.M., Vishkin U.: Fast string matching with k differences. Journal of Computer and System Sciences 37(1)/1988, 63–78.
Google Scholar
Susik R., Grabowski S., Fredriksson K.: Multiple Pattern Matching Revisited. Proceedings of PSC 2014, 59–70.
Google Scholar
Ukkonen E.: Approximate string-matching with q-grams and maximal matches. Theoretical Computer Science 92/1992, 191–211.
Google Scholar
Statystyki
Abstract views: 181PDF downloads: 125
Licencja
Utwór dostępny jest na licencji Creative Commons Uznanie autorstwa – Na tych samych warunkach 4.0 Miedzynarodowe.
