Algoritmus Commentz-Walter - Commentz-Walter algorithm

v počítačová věda, Algoritmus Commentz-Walter je algoritmus prohledávání řetězců vynalezl Beate Commentz-Walter.[1] Jako Algoritmus shody řetězců Aho – Corasick, může vyhledávat více vzorů najednou. Kombinuje nápady od společnosti Aho – Corasick s rychlým spojením Algoritmus vyhledávání řetězců Boyer – Moore. Pro text délky n a maximální délka vzoru m, jeho nejhorší doba provozu je Ó (mn), ačkoli průměrný případ je často mnohem lepší.[2]

GNU grep implementuje algoritmus shody řetězců velmi podobný Commentz-Walterovi.[3]

Reference

  1. ^ Commentz-Walter, Beate (1979). Algoritmus shody řetězců v průměru rychlý. Mezinárodní kolokvium o automatech, jazycích a programování. LNCS. 71. Graz, Rakousko: Springer. str. 118–132. doi:10.1007/3-540-09510-1_10. ISBN  3-540-09510-1.
  2. ^ Watson, Bruce William (1995-09-15). Taxonomie a sady nástrojů algoritmů běžného jazyka. Eindhoven University of Technology. doi:10,6100 / IR444299. ISBN  90-386-0396-7.
  3. ^ "src / kwset.c: vyhledat libovolné ze sady klíčových slov". GNU grep. Srpna 1989. Citováno 2020-07-14.

externí odkazy