Kraussův algoritmus porovnávání zástupných znaků - Krauss wildcard-matching algorithm - Wikipedia

v počítačová věda, Kraussův algoritmus porovnávání zástupných znaků je porovnávání vzorů algoritmus. Založeno na syntaxe zástupných znaků při běžném používání, např. v Microsoft Windows rozhraní příkazového řádku, algoritmus poskytujerekurzivní mechanismus pro porovnávání vzorů v softwarových aplikacích, založený na syntaxi jednodušší, než jakou obvykle nabízí regulární výrazy.

Dějiny

Algoritmus je založen na historii vývoje, testování správnosti a výkonu a zpětné vazbě programátora, která začala neúspěšným hledáním spolehlivého nerekurzivního algoritmu pro porovnávání zástupných znaků. Počáteční algoritmus, implementovaný v jedné smyčce while, rychle vyzval komentáře vývojářů softwaru, což vedlo k vylepšení.[1] Probíhající komentáře a návrhy[2][3] vyvrcholila revidovaným algoritmem stále implementovaným v jedné smyčce while, ale vylepšená na základě kolekce testovací případy a a výkonnostní profiler.[4] Zkušenosti s laděním smyčky single while pomocí profileru vyvolaly vývoj strategie se dvěma smyčkami, která dosáhla dalšího zvýšení výkonu, zejména v situacích zahrnujících prázdné vstupní řetězce nebo vstup neobsahující žádné zástupné znaky.[5] Algoritmus dvou smyček je k dispozici pro použití open-source software rozvojová komunita podle podmínek Licence Apache v. 2.0 a je doprovázen kódem testovacího případu.

Používání

Algoritmus zpřístupněný pod licencí Apache je implementován v obou ukazatel -na základě C ++ a přenosný C ++ (implementován bez ukazatelů). Kód testovacího případu, který je k dispozici také pod licencí Apache, lze použít na jakýkoli algoritmus, který poskytuje níže uvedené operace shody vzorů. Implementaci v kódovaném stavu nelze zpracovat vícebajtové znakové sady a představuje problémy, když prohledávaný text může obsahovat více nekompatibilních znakových sad.

Operace porovnávání vzorů

Algoritmus podporuje tři operace porovnávání vzorů:

  • Mezi vzorem a zdrojem, který má být zkontrolován na shodu, se provádí shoda jedna ku jedné, s výjimkou hvězdičky (* ) nebo otazník (? ) znaky ve vzoru.
  • Hvězdička (* ) znak odpovídá libovolné sekvenci s nulovým nebo více znaky.
  • Otazník (? ) znak odpovídá libovolnému jednomu znaku.

Příklady

  • * foo * odpovídá libovolnému řetězci obsahujícímu "foo".
  • mini * odpovídá libovolnému řetězci, který začíná řetězcem „mini“ (včetně samotného řetězce „mini“).
  • ???* odpovídá libovolnému řetězci tří nebo více písmen.

Aplikace

Původní algoritmus byl přenesen do souboru DataFlex programovací jazyk Larry Heiges[6] pro použití s Přístup k datům po celém světě knihovna kódů. Byl zveřejněn na GitHubu v upravené podobě jako součást čtečky log souborů.[7] Algoritmus roku 2014 je součástí prohlížeče Unreal Model Viewer zabudovaného do epických her Neskutečný motor herní engine.[8][9]

Viz také

Reference

  1. ^ Krauss, Kirk (2008). „Odpovídající zástupné znaky: Algoritmus“. Dr. Dobb's Journal.
  2. ^ "hledání divokých karet". alt.os.rozvoj. 2008.
  3. ^ T.J. (2014). "shoda divoké karty v textovém řetězci". Přetečení zásobníku.
  4. ^ Krauss, Kirk (2014). „Odpovídající zástupné znaky: Empirický způsob, jak zkrotit algoritmus“. Dr. Dobb's Journal.
  5. ^ Krauss, Kirk (2018). „Odpovídající zástupné znaky: Vylepšený algoritmus pro velká data“. Vývoj pro výkon.
  6. ^ Heiges, Larry (2008). "Funkce porovnání textu - generalTextCompare.txt". Data Access Worldwide Code Library.
  7. ^ Deniskore (2013). „Deniskore / wildcard / CLogReader.cpp“. Populární úložiště. GitHub. Řádky 173-279.
  8. ^ gildor2 (2016). „UModel / Core / Core.cpp“. Prohlížeč modelu Unreal Engine (prohlížeč UE). GitHub. Řádky 334-435.
  9. ^ gildor2 (2016). „History for UModel / Core / Core.cpp“. Prohlížeč modelu Unreal Engine (prohlížeč UE).