In computer science, the Commentz-Walter algorithm is a string searching algorithm invented by . Like the Aho–Corasick string matching algorithm, it can search for multiple patterns at once. It combines ideas from Aho–Corasick with the fast matching of the Boyer–Moore string search algorithm. For a text of length n and maximum pattern length of m, its worst-case running time is O(mn), though the average case is often much better. GNU grep once implemented a string matching algorithm very similar to Commentz-Walter.
Attributes | Values |
---|
rdf:type
| |
rdfs:label
| - Commentz-Walter algorithm (en)
- Алгоритм Коменц-Вальтер (uk)
|
rdfs:comment
| - In computer science, the Commentz-Walter algorithm is a string searching algorithm invented by . Like the Aho–Corasick string matching algorithm, it can search for multiple patterns at once. It combines ideas from Aho–Corasick with the fast matching of the Boyer–Moore string search algorithm. For a text of length n and maximum pattern length of m, its worst-case running time is O(mn), though the average case is often much better. GNU grep once implemented a string matching algorithm very similar to Commentz-Walter. (en)
- Алгоритм Коменц-Вальтер (англ. Commentz-Walter) — запропонований Беатою Коменц-Вальтер алгоритм пошуку рядка. Подібно до алгоритму Ахо-Корасік може шукати водночас декілька підрядків у рядку. Оснований на алгоритмі Бояра-Мура. Алгоритм Коменц-Вальтер важливий зокрема тим, що був реалізований у другій версії Юнікс-утиліти grep. Оцінки практичної швидкодії алгоритму різняться: за одними оцінками, його швидкодія не перевищує швидкодію алгоритму Ахо-Корасік. За іншими оцінками, його швидкодія в багатьох випадках значно перевищує швидкодію алгоритму Ахо-Корасік. (uk)
|
foaf:depiction
| |
dct:subject
| |
Wikipage page ID
| |
Wikipage revision ID
| |
Link from a Wikipage to another Wikipage
| |
sameAs
| |
dbp:wikiPageUsesTemplate
| |
thumbnail
| |
has abstract
| - In computer science, the Commentz-Walter algorithm is a string searching algorithm invented by . Like the Aho–Corasick string matching algorithm, it can search for multiple patterns at once. It combines ideas from Aho–Corasick with the fast matching of the Boyer–Moore string search algorithm. For a text of length n and maximum pattern length of m, its worst-case running time is O(mn), though the average case is often much better. GNU grep once implemented a string matching algorithm very similar to Commentz-Walter. (en)
- Алгоритм Коменц-Вальтер (англ. Commentz-Walter) — запропонований Беатою Коменц-Вальтер алгоритм пошуку рядка. Подібно до алгоритму Ахо-Корасік може шукати водночас декілька підрядків у рядку. Оснований на алгоритмі Бояра-Мура. Алгоритм Коменц-Вальтер важливий зокрема тим, що був реалізований у другій версії Юнікс-утиліти grep. Оцінки практичної швидкодії алгоритму різняться: за одними оцінками, його швидкодія не перевищує швидкодію алгоритму Ахо-Корасік. За іншими оцінками, його швидкодія в багатьох випадках значно перевищує швидкодію алгоритму Ахо-Корасік. Якщо замість алгоритму Бояра-Мура взяти за основу алгоритм Бояра-Мура-Горспула, то алгоритм Коменц-Вальтер можна дещо спростити, однак його швидкодія для рядка довжиною n та найдовшого ключа L, в найгіршому випадку залишатиметься на рівні O(n × L). (uk)
|
gold:hypernym
| |
prov:wasDerivedFrom
| |
page length (characters) of wiki page
| |
foaf:isPrimaryTopicOf
| |
is Link from a Wikipage to another Wikipage
of | |
is Wikipage redirect
of | |
is foaf:primaryTopic
of | |