Ir a navegaciónSaltar a buscar
En informática , el algoritmo Commentz-Walter es un algoritmo de búsqueda de cadenas inventado por Beate Commentz-Walter . [1] Al igual que el algoritmo de coincidencia de cadenas de Aho-Corasick , puede buscar varios patrones a la vez. Combina ideas de Aho-Corasick con la rápida coincidencia del algoritmo de búsqueda de cadenas de Boyer-Moore . Para un texto de longitud n y longitud máxima de patrón de m , su tiempo de ejecución en el peor de los casos es O ( mn ), aunque el caso promedio suele ser mucho mejor. [2]
GNU grep implementa un algoritmo de coincidencia de cadenas muy similar a Commentz-Walter. [3]
Referencias
- ^ Commentz-Walter, Beate (1979). Un algoritmo de coincidencia de cadenas rápido en promedio . Coloquio Internacional sobre Autómatas, Lenguajes y Programación . LNCS . 71 . Graz, Austria: Springer. págs. 118-132. doi : 10.1007 / 3-540-09510-1_10 . ISBN 3-540-09510-1.
- ↑ Watson, Bruce William (15 de septiembre de 1995). Taxonomías y conjuntos de herramientas de algoritmos de lenguaje regular . Universidad Tecnológica de Eindhoven . doi : 10.6100 / IR444299 . ISBN 90-386-0396-7.
- ^ "src / kwset.c: busque cualquiera de un conjunto de palabras clave" . GNU grep . Agosto de 1989 . Consultado el 14 de julio de 2020 .
Enlaces externos
- Un algoritmo de coincidencia de cadenas rápido en promedio en la Wayback Machine (archivado el 10 de octubre de 2017)
- "Rendimiento de algoritmos de coincidencia de cadenas múltiples en minería de texto" . Marzo de 2017. doi : 10.1007 / 978-981-10-3156-4_71 .
 | Este artículo relacionado con algoritmos o estructuras de datos es un código auxiliar . Puedes ayudar a Wikipedia expandiéndolo . |