Алгоритм Коменц-Вальтер

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

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

Примітки[ред.ред. код]

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

Література[ред.ред. код]

Посилання[ред.ред. код]