Nowe algorytmy wyszukiwania dokładnego i przybliżonego

• Autorzy: Grabowski S.

Warianty tytułu

EN

New algorithms for exact and approximate text matching

• Języki publikacji: PL

Abstrakty

PL

Praca przedstawia główne wyniki z tematyki algorytmów tekstowych otrzymane w Katedrze Informatyki Stosowanej w latach 2004-2009. Algorytmy te dotyczą wybranych rozmaitych problemów wyszukiwania dokładnego i przybliżonego, również w intensywnie w ostatnich latach badanym scenariuszu z wykorzystaniem kompresji.

EN

This work presents main results in the domain of text algorithms obtained in Computer Engineering Dept. in the years 2004-2009. The algorithms concern various exact and approximate string matching problems, also in the recently actively developed scenario involving compression.

Słowa kluczowe

PL

algorytmy wyszukiwania; wyszukiwanie dokładne; wyszukiwanie przybliżone

EN

algorithms for text maching; exact text maching; approximate text maching

• Wydawca: Wydawnictwo Politechniki Łódzkiej
• Czasopismo: Zeszyty Naukowe. Elektryka / Politechnika Łódzka
• Rocznik: 2010
• Tom: z. 121
• Strony: 451--462
• Opis fizyczny: Bibliogr. 26 poz.

Twórcy

autor

Grabowski S.

• Wydział Elektrotechniki, Elektroniki, Informatyki i Automatyki Politechniki Łódzkiej

Bibliografia

• [1] Navarro G., Raffinot M.: Flexible Pattern Matching in Strings - Practical on-line search algorithms for texts and biological sequences. Cambridge University Press, 2002.
• [2] Grabowski Sz.: New Algorithms for Exact and Approximate Text Matching. Wydawnictwo Politechniki Łódzkiej, 2009.
• [3] Cormen T.H., Leiserson C.E., Rivest R.L., Stein C: Wprowadzenie do algorytmów. Wydawnictwa Naukowo-Techniczne, Warszawa 2004.
• [4] Baeza-Yates R.A., Gonnet G.H.: A New Approach to Text Searching. Proc. 12th Int. Conference on Research and Development in Information Retrieval (SIGIR), str. 168-175. ACM Press, 1989.
• [5] Navarro G., Raffinot M.: Fast and flexible string matching by combining bit-parallelism and suffix automata. ACM Journal of Experimental Algorithmics, 5(4), 2000.
• [6] Fredriksson K., Grabowski Sz.: Practical and optimal string matching. Proc. String Processing and Information Retrieval Conference (SPIRE), LNCS 3772, str. 374-385, Springer, 2005.
• [7] Fredriksson K., Grabowski Sz.: Average-optimal string matching. Journal of Discrete Algorithms, 7(4):579-594, 2009.
• [8] Holub J., Durian B.: Fast Variants of Bit Parallel Approach to Suffix Automata. Talk given in The Second Haifa Annual International Stringology Research Workshop of the Israeli Science Foundation, 2005.
• [9] Grabowski Sz., Fredriksson K.: Bit parallel string matching under Hamming distance in O(n-m/ w¬) worst case time. Information Processing Letters, 105(5): 182-187, 2008.
• [10] Baeza-Yates R.A., Gonnet G.H.: A New Approach to Text Searching. Communications of the ACM, 35(10): 74-82, 1992.
• [11] Fredriksson K., Grabowski Sz.: Nested Counters in Bit-Parallel String Matching. Proc. 3rd Int. Conference on Language and Automata Theory and Applications (LATA), LNCS 5457, str. 338-349, Springer, 2009.
• [12] Navarro G., Grabowski Sz., Makinen V., Deorowicz S.: Improved Time and Space Complexities for Transposition Invariant String Matching, Technical Report TR/DCC-2005-4, University of Chile, Department of Computer Science, 2005.
• [13] Grabowski Sz., Deorowicz S.: Nice to.be a chimera: A hybrid algorithm for the longest common transposition-invariant subsequence problem. Proc. Int. Conference on Modern Problems of Radio Engineering, Telecommunications, and Computer Science (TCSET), str. 50-54, Lviv, Ukraina, 2008.
• [14] Deorowicz S., Grabowski Sz.: A hybrid algorithm for the longest common transposition-invariant subsequence problem. Computing and Informatics, 28, str. 129-11 A, 2009.
• [15] Fredriksson K., Grabowski Sz.: Efficient Bit-parallel Algorithms for (β;α) -matching. Proc. Int. Workshop on Experimental and Efficient Algorithms (WEA), LNCS 4007, str. 170-181, Springer, 2006.
• [16] Fredriksson K., Grabowski Sz.: Efficient algorithms for (β;γ;α)-matching. Proc. Prague Stringology Conference (PSC), str. 29-40, Prague, Czechy, 2006.
• [17] Fredriksson K., Grabowski Sz.: Efficient algorithms for pattern matching with general gaps and character classes. Proc. String Processing and Information Retrieval Conference (SPIRE), LNCS 4209, str. 267-278, Springer, 2006. (Nagroda za najlepszy artykuł.).
• [18] Fredriksson K., Grabowski Sz.: Efficient Algorithms for (β;γ;α) and (β;k∆;α)-matching. International Journal of Foundations of Computer Science, 19(1):163-183, 2008.
• [19] Fredriksson K., Grabowski Sz.: Efficient algorithms for pattern matching with general gaps, character classes and transposition invariance. Information Retrieval, 11(4), str. 335-357, 2008.
• [20] Fredriksson K., Grabowski Sz.: A general compression algorithm that supports fast searching. Information Processing Letters, 100(6):226-232, 2006.
• [21] Grabowski Sz.: Making dense codes even denser. AGH Automatyka, tom12, zeszyt 3, str. 769-779, 2008.
• [22] Brisaboa N., Farina A., Navarro G., Esteller M.: (S,C)-Dense Coding: An Optimized Compression Code for Natural Language Text Databases. Proc. String Processing and Information Retrieval Conference (SPIRE), LNCS 2857, str. 122-136, Springer, 2003.
• [23] Grabowski Sz., Makinen V., Navarro G.: First Huffman, then Burrows-Wheeler: A Simple Alphabet-Independent FM-Index. Proc. String Processing and Information Retrieval Conference (SPIRE), LNCS 3246, str. 210-211, Springer, 2004.
• [24] Grabowski Sz., Makinen V., Navarro G., Salinger A.: A Simple Alphabet-Independent FM-index, Proc. Prague Stringology Conference (PSC), str. 230-244, Prague, Czechy, 2005.
• [25] Przywarski R., Grabowski Sz., Navarro G., Salinger A.: FM-KZ: An even simpler alphabet-independent FM-index. Proc. Prague Stringology Conference (PSC), str. 226-241, Prague, Czechy, 2006.
• [26] Grabowski Sz., Navarro G., Przywarski R., Salinger A., Makinen V.: A Simple Alphabet-independent FM-index, International Journal of Foundations of Computer Science, 17(6): 1365-1384, 2006.