Алгоритм Коменц Вальтер англ Commentz Walter запропонований Беатою Коменц Вальтер алгоритм пошуку рядка Подібно до алгор

Алгоритм Коменц-Вальтер (англ. Commentz-Walter) — запропонований Беатою Коменц-Вальтер алгоритм пошуку рядка. Подібно до алгоритму Ахо-Корасік може шукати водночас декілька підрядків у рядку.

Оснований на алгоритмі Бояра-Мура. Алгоритм Коменц-Вальтер важливий зокрема тим, що був реалізований у другій версії Юнікс-утиліти grep.

Оцінки практичної швидкодії алгоритму різняться: за одними оцінками, його швидкодія не перевищує швидкодію алгоритму Ахо-Корасік. За іншими оцінками, його швидкодія в багатьох випадках значно перевищує швидкодію алгоритму Ахо-Корасік.

Якщо замість алгоритму Бояра-Мура взяти за основу алгоритм Бояра-Мура-Горспула, то алгоритм Коменц-Вальтер можна дещо спростити, однак його швидкодія для рядка довжиною n та найдовшого ключа L, в найгіршому випадку залишатиметься на рівні O(n × L).

Примітки

(Gusfield; С. 55)
(Bruce Watson, 1995; С. 83)
(Gusfield; С. 56)

Література

Gusfield, Dan (1999), Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge University Press, ISBN .
Watson, Bruce (1995). 4.4 The Commentz-Walter algorithms. (PDF). Eindhoven, The Netherlands: Eindhoven University of Technology. с. 393. Архів оригіналу (PDF) за 24 березня 2012. Процитовано 5 серпня 2013.

Посилання

Beate Commentz-Walter — оригінальна публікація алгоритму.

Це незавершена стаття про алгоритми.
Ви можете проєкту, виправивши або дописавши її.

[1] (Gusfield; С. 55)

[2] (Bruce Watson, 1995; С. 83)

[3] (Gusfield; С. 56)