Algorytm dopasowywania symboli wieloznacznych Kraussa
W informatyce algorytm dopasowywania symboli wieloznacznych Kraussa jest algorytmem dopasowywania wzorców . W oparciu o powszechnie używaną składnię symboli wieloznacznych , np. w interfejsie wiersza poleceń systemu Microsoft Windows , algorytm zapewnia nierekurencyjny mechanizm dopasowywania wzorców w aplikacjach, oparty na składni prostszej niż typowa dla wyrażeń regularnych .
Historia
Algorytm opiera się na historii rozwoju, testowaniu poprawności i wydajności oraz opiniach programistów, które rozpoczęły się od nieudanych poszukiwań niezawodnego nierekurencyjnego algorytmu dopasowywania symboli wieloznacznych. Początkowy algorytm, zaimplementowany w pojedynczej pętli while, szybko wywołał komentarze twórców oprogramowania, co doprowadziło do ulepszeń. Bieżące komentarze i sugestie zakończyły się poprawionym algorytmem, nadal zaimplementowanym w pojedynczej pętli while, ale udoskonalonym na podstawie zbioru przypadków testowych i profilera wydajności . Doświadczenie w dostrajaniu pojedynczej pętli while za pomocą narzędzia do profilowania skłoniło do opracowania strategii z dwiema pętlami, która umożliwiła dalszy wzrost wydajności, szczególnie w sytuacjach obejmujących puste ciągi wejściowe lub dane wejściowe niezawierające symboli wieloznacznych. Algorytm dwóch pętli jest dostępny do użytku przez programistów open source na warunkach licencji Apache w wersji 2.0 i towarzyszy mu kod przypadku testowego.
Stosowanie
Algorytm udostępniony na licencji Apache jest zaimplementowany zarówno w C++ opartym na wskaźnikach , jak i C++ przenośnym (implementowanym bez wskaźników). Kod przypadku testowego, dostępny również na licencji Apache, można zastosować do dowolnego algorytmu, który udostępnia poniższe operacje dopasowywania wzorców. Implementacja w postaci zakodowanej nie jest w stanie obsłużyć zestawów znaków wielobajtowych i stwarza problemy, gdy wyszukiwany tekst może zawierać wiele niekompatybilnych zestawów znaków.
Operacje dopasowywania wzorców
Algorytm obsługuje trzy operacje dopasowywania wzorców:
- Dopasowanie jeden do jednego jest przeprowadzane między wzorcem a źródłem, które ma zostać sprawdzone pod kątem dopasowania, z wyjątkiem znaków gwiazdki ( * ) lub znaku zapytania ( ? ) we wzorcu.
- Znak gwiazdki ( * ) pasuje do dowolnej sekwencji zerowej lub większej liczby znaków.
- Znak zapytania ( ? ) pasuje do dowolnego pojedynczego znaku.
Przykłady
- *foo* dopasowuje dowolny ciąg zawierający „foo”.
- mini* dopasowuje dowolny ciąg rozpoczynający się od „mini” (w tym sam ciąg „mini”).
- ???* pasuje do dowolnego ciągu trzech lub więcej liter.
Aplikacje
Oryginalny algorytm został przeniesiony do języka programowania DataFlex przez Larry'ego Heigesa do użytku z biblioteką kodów Data Access Worldwide . Został opublikowany na GitHub w zmodyfikowanej formie jako część czytnika plików dziennika. Algorytm 2014 jest częścią przeglądarki Unreal Model Viewer wbudowanej w silnik gry Epic Games Unreal Engine .