Algoritmo de conteo de ocurrencia de cadenas

Tengo curiosidad por saber cuál es el algoritmo más eficiente (o comúnmente usado) para contar el número de ocurrencias de una cadena en una porción de texto.

Por lo que leí , el algoritmo de búsqueda de cadenas de Boyer-Moore es el estándar para las búsquedas de cadenas, pero no estoy seguro de que contar las ocurrencias de una manera eficiente sea lo mismo que buscar una cadena.

En Python esto es lo que quiero:

text_chunck = "one two three four one five six one" occurance_count(text_chunck, "one") # gives 3. 

EDITAR: Parece que python str.count sirve como tal método; sin embargo, no puedo encontrar qué algoritmo utiliza.

Para empezar, sí, puedes lograr esto con Boyer-Moore de manera muy eficiente. Sin embargo, dependiendo de algunos otros parámetros de su problema, podría haber una mejor solución.

El algoritmo de coincidencia de cadenas Aho-Corasick encontrará todas las apariciones de un conjunto de cadenas de patrones en una cadena objective y lo hace en el tiempo O (m + n + z), donde m es la longitud de la cadena a buscar, n es la combinación longitud de todos los patrones a coincidir, y z es el número total de coincidencias producidas. Esto es lineal en el tamaño de las cadenas de origen y destino si solo tiene una cadena para que coincida. También encontrará apariciones superpuestas de la misma cadena. Además, si desea verificar cuántas veces aparece un conjunto de cadenas en una cadena de origen, solo necesita hacer una llamada al algoritmo. Además de esto, si el conjunto de cadenas que desea buscar nunca cambia, puede hacer que O (n) funcione como tiempo de preprocesamiento y luego encontrar todas las coincidencias en O (m + z).

Si, por otro lado, tiene una cadena de origen y un conjunto de subcadenas en rápido cambio para buscar, es posible que desee utilizar un árbol de sufijos . Con el tiempo de preprocesamiento O (m) en la cadena en la que buscará, puede, en tiempo O (n) por subcadena, verificar cuántas veces aparece una subcadena particular de longitud n en la cadena.

Finalmente, si está buscando algo que pueda codificar fácilmente y con una molestia mínima, puede considerar buscar en el algoritmo Rabin-Karp , que utiliza una función de rollo de hash para encontrar cadenas. Esto se puede codificar en aproximadamente diez a quince líneas de código, no tiene tiempo de preprocesamiento, y para cadenas de texto normales (un montón de texto con pocas coincidencias) puede encontrar todas las coincidencias muy rápidamente.

¡Espero que esto ayude!

Boyer-Moore sería una buena opción para contar las incidencias, ya que tiene algunos gastos generales que solo necesitaría hacer una vez. Se hace mejor cuanto más larga sea la cadena del patrón, por lo que para “uno” no sería una buena opción.

Si desea contar las superposiciones, comience la siguiente búsqueda un carácter después de la coincidencia anterior. Si desea ignorar las superposiciones, comience la siguiente búsqueda en la longitud de la cadena del patrón completo después de la coincidencia anterior.

Si su idioma tiene un método indexOf o strpos para encontrar una cadena en otra, puede usarlo. Si se demora, entonces elige un mejor algoritmo.

Hellnar, puedes usar un diccionario simple para contar las ocurrencias en una Cadena. El algoritmo es un algoritmo de conteo, aquí hay un ejemplo:

 """ The counting algorithm is used to count the occurences of a character in a string. This allows you to compare anagrams and strings themselves. ex. animal, lamina a=2,n=1,i=1,m=1 """ def count_occurences(str): occurences = {} for char in str: if char in occurences: occurences[char] = occurences[char] + 1 else: occurences[char] = 1 return occurences def is_matched(s1,s2): matched = True s1_count_table = count_occurences(s1) for char in s2: if char in s1_count_table and s1_count_table[char]>0: s1_count_table[char] -= 1 else: matched = False break return matched #counting.is_matched("animal","laminar") 

Este ejemplo simplemente devuelve Verdadero o Falso si las cadenas coinciden. Tenga en cuenta que este algoritmo cuenta la cantidad de veces que un carácter aparece en una cadena, esto es bueno para los anagtwigs.