Hirschberg's algorithm for approximate matching

• Autorzy: Drozdek A.

Warianty tytułu

PL

Algorytm Hirschberga dla problemu przybliżonego wyszukiwania wzorca

• Języki publikacji: EN

Abstrakty

EN

The Hirschberg algorithm was devised to solve the longest common subsequence problem. The paper discusses the way of adopting the algorithm to solve the string matching problem in linear space to determine edit distance for two strings and their alignment.

PL

Algorytm Hirschberga został podany w celu rozwiązania problemu najdłuższego wspólnego podciągu. Niniejszy artykuł prezentuje sposób zaadoptowania tego algorytmu do rozwiązania przy liniowych wymogach pamięciowych problemu wyszukiwania wzorca w celu znalezienia odległości edycyjnej dwóch tekstów i ich wyrównania.

Słowa kluczowe

EN

pattern matching; string processing; edit distance; Hirschberg's algorithm

PL

wyszukiwanie wzorca; przetwarzanie tekstów; odległość edycyjna; algorytm Hirschberga

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2002
• Tom: Vol. 4
• Strony: 91--100
• Opis fizyczny: Bibliogr. 5 poz.

Twórcy

autor

Drozdek A.

• Department of Mathematics and Computer Science, Duquesne University, Pittsburgh

Bibliografia

• [1] Crochemore M., Rytter W.: Text algorithms. New York, Oxford University Press 1994
• [2] Gusfield D.: Algorithms on strings, trees, and sequences. New York, Cambridge University Press 1997
• [3] Hirschberg D.S.: A linear-space algorithm for computing maximal common subsequences. Communications of the ACM, 18,1975,341-343
• [4] Stephen G.A.: String searching algorithms. Singapore, World Scientific 1994
• [5] Wagner R.A., Fischer M.J.: The string-to-string correction problem. Journal of the ACM, 21, 1974, 168-173