Skompresowane dopasowanie wzorca

W informatyce dopasowywanie skompresowanych wzorców (w skrócie CPM ) to proces wyszukiwania wzorców w skompresowanych danych z niewielką lub żadną dekompresją . Wyszukiwanie w ciągu skompresowanym jest szybsze niż przeszukiwanie ciągu nieskompresowanego i wymaga mniej miejsca.

Skompresowany problem z dopasowaniem

Jeśli skompresowany plik używa kodowania o zmiennej szerokości, może to stanowić problem: na przykład niech „100” będzie słowem kodowym dla a i niech „110100” będzie słowem kodowym dla b . Jeśli szukamy wystąpienia a w tekście, możemy otrzymać również wystąpienie, które mieści się w słowie kodowym b : zdarzenie to nazywamy fałszywym dopasowaniem . Musimy więc sprawdzić, czy wykryte wystąpienie jest skutecznie wyrównane na granicy słowa kodowego. Zawsze jednak moglibyśmy zdekodować cały tekst, a następnie zastosować klasyczny algorytm dopasowywania ciągów znaków , ale zwykle wymaga to więcej miejsca i czasu i często nie jest możliwe, na przykład, jeśli skompresowany plik jest hostowany online. Ten problem weryfikacji dopasowania zwróconego przez skompresowany algorytm dopasowywania wzorców jest prawdziwym lub fałszywym dopasowaniem wraz z niemożnością zdekodowania całego tekstu nazywany jest skompresowanym problemem dopasowania .

Strategie

Istnieje wiele strategii znajdowania granic słów kodowych i unikania pełnej dekompresji tekstu, na przykład:

• Lista indeksów pierwszego bitu każdego słowa kodowego, gdzie możemy zastosować wyszukiwanie binarne;
• Lista indeksów pierwszego bitu każdego słowa kodowego z kodowaniem różnicowym, dzięki czemu możemy zająć mniej miejsca w pliku;
• Maska bitu , gdzie bit 1 oznacza początkowy bit każdego słowa kodowego;
• Podział na bloki dla częściowej i celowej dekompresji.

Wprowadzono algorytmy zapewniające czas działania, który rośnie logarytmicznie wraz ze wzrostem długości łańcucha i wzoru.

• Shmuel T. Klein i Dana Shapira DOPASOWANIE WZORÓW W TEKSTACH ZAKODOWANYCH HUFFMANA (2003)
• Marek Karpiński, Wojciech Rytter i Ayumi Shinohara. WYDAJNY ALGORYTM DOPASOWUJĄCY DO WZORCÓW DLA ŁAŃCUCHÓW Z KRÓTKIMI OPISAMI. Nordic Journal of Computing 4 (2): s. 172-168 (1997).

Linki zewnętrzne

•   „Prawie optymalne dopasowanie wzorca w pełni skompresowanego LZW” . 1999: 316–325. CiteSeerX 10.1.1.44.5521 . {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )
• Skompresowany algorytm dopasowywania wzorców oparty na słowniku (PDF) , zarchiwizowany z oryginału (PDF) 13 marca 2003 r.
•   „Unifikująca struktura do dopasowywania skompresowanych wzorców”. 1999: 89–96. CiteSeerX 10.1.1.50.1745 . {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )
• „Przyspieszenie dopasowywania wzorców ciągów przez kompresję tekstu: Świt nowej ery” (PDF) . Zarchiwizowane od oryginału (PDF) w dniu 08.08.2007 . Źródło 2009-03-22 . {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )
•   „Zmiana i podejście do dopasowywania wzorców w tekście skompresowanym LZW”. 1999: 1–13. CiteSeerX 10.1.1.15.4609 . {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )
• „Algorytm LZW” (PDF) . {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )