Czy kiedykolwiek używałeś algorytmów KMP lub BM? - algorytm

Wiem, że algorytmy KMP (Knuth-Morris-Pratt) i BM (Boyers-Moore) są dobrymi algorytmami wyszukiwania ciągów. Wiem też, że BM jest 3-5 razy szybszy od KMP.

Czy kiedykolwiek korzystałeś z algorytmów BM lub KMP? Czy algorytm ma tutaj naprawdę znaczenie?

Odpowiedzi:

Jeśli spojrzysz na przykład na funkcję String.indexOf Java, wydaje się, że używają metody brute force do dopasowywania ciągów. Możesz się zastanawiać, dlaczego tak jest.

Powodem jest to, że niektóre preprocessing zapytania jestwykonywane w tych algorytmach i mogą być kosztowne (szczególnie dla BM, jeśli używasz obu tablic). Dlatego szukane ciągi muszą mieć duży rozmiar, zanim KMP i BM mogą wyłapać metodę brute force.

Zawsze jest handel, gdy używasz innegoAlgorytmy i w przypadku dużych ciągów można rozważyć indeksowanie tekstu, a nie kwerendy (np. drzewa przyrostków). Może to być nawet przydatne, gdy za każdym razem zajmujesz się nowymi tekstami.

Moim zdaniem te algorytmy są raczej akademickie i użyteczne tylko w szczególnych okolicznościach.

glibc strstr funkcja jest liniowa. Używa a Algorytm dwukierunkowy, co moim zdaniem jest odmianą Boyer-Moore. Sądzę, że to sprawia, że ​​ktoś używa strstr w gcc faktycznie używa szybkiego algorytmu wyszukiwania ciągów w świecie rzeczywistym.

Jeśli chodzi o pytanie, czy szybki algorytmma znaczenie, IMHO ma znaczenie tylko wtedy, gdy wielkość danych jest wystarczająco duża. Wiele z jawnie wykonywanych operacji na łańcuchach to bardzo małe ciągi (powiedzmy mniej niż 500 znaków). Nie oznacza to, że nie wykonujemy ciężkich operacji na ciągach znaków (np. Wyszukiwanie pełnotekstowe w bazie danych), ale w tym przypadku zazwyczaj pozwalamy, aby baza danych lub biblioteka wykonywała dla nas duże operacje. Baza danych lub biblioteka używa szybkiego wyszukiwania ciągów znaków algorytmy - więc nie powiedziałbym, że nie mają znaczenia, tylko że jego użycie nie jest dla nas bezpośrednio widoczne.

Zaimplementowałem kiedyś KMP na sprzęcie. Jeśli sprzęt jest układem FPGA, możesz użyć rekonfigurowalności, aby mieć obwód samodomodujący. Obwody te otrzymują ciąg wyszukiwania. Następnie dokonaj koniecznego wstępnego przerobienia w sprzęcie i ponownie skonfiguruj się do logiki, która ostro dokonuje KMP. Ale tutaj również konieczne jest zaindeksowanie dużej ilości danych, aby przyspieszyć, ale jest coś takiego (np. Dopasowanie DNA).