una strlwr saber minusculas minuscula mayusculas mayuscula letra convertir contar comparar como caracteres cadenas cadena c++ string windows algorithm

strlwr - El algoritmo C++ más rápido para la prueba de cadenas contra una lista de semillas predefinidas(sin distinción entre mayúsculas y minúsculas)



convertir una letra en mayuscula c++ (7)

Como el número de cadenas no es grande (~ 100), puede usar el siguiente algoritmo:

  1. Calcule la longitud máxima de la palabra que tiene. Deja que sea N.
  2. Crear int checks[N]; matriz de suma de comprobación.
  3. La suma de comprobación será la suma de todos los caracteres en la frase de búsqueda. Por lo tanto, puede calcular dicha suma de verificación para cada palabra de su lista (que se conoce en tiempo de compilación) y crear std::map<int, std::vector<std::wstring>> , donde int es la suma de verificación de la cadena, y vector debe contener todas sus cadenas con esa suma de verificación. Cree una matriz de dichos mapas para cada longitud (hasta N), también se puede hacer en tiempo de compilación.
  4. Ahora muévase sobre una cuerda grande con el puntero. Cuando el puntero apunta al carácter X, debe agregar el valor de X char a todos los números enteros de checks , y para cada uno de ellos (números del 1 al N) eliminar el valor del carácter (XK), donde K es el número entero en la matriz de checks . Por lo tanto, siempre tendrá una suma de verificación correcta para toda la longitud almacenada en la matriz de checks . Después de esa búsqueda en el mapa, existen cadenas con dicho par (longitud y suma de verificación), y si existe, compárelo.

Debería dar un resultado falso positivo (cuando la suma de comprobación y la longitud son iguales, pero la frase no lo es) muy raro.

Entonces, digamos que R es la longitud de una cuerda grande. Luego, pasar sobre él tomará O (R). En cada paso, realizará N operaciones con "+" número pequeño (valor de carácter), N operaciones con "-" número pequeño (valor de carácter), que es muy rápido. Cada paso tendrá que buscar el contador en la matriz de checks , y ese es O (1), porque es un bloque de memoria.

Además, en cada paso tendrá que encontrar el mapa en la matriz del mapa, que también será O (1), porque también es un bloque de memoria. Y dentro del mapa, tendrá que buscar una cadena con la suma de verificación correcta para el registro (F), donde F es el tamaño del mapa, y generalmente no contendrá más de 2-3 cadenas, por lo que en general podemos pretender que también es O (1)

También puede verificar, y si no hay cadenas con la misma suma de verificación (eso debería suceder con una alta probabilidad con solo 100 palabras), puede descartar el mapa, almacenando pares en lugar de mapa.

Entonces, finalmente eso debería dar O (R), con una O bastante pequeña. Esta forma de calcular la checksum de checksum se puede cambiar, pero es bastante simple y completamente rápido, con reacciones falsas positivas realmente raras.

Tengo una lista de cadenas de semillas, alrededor de 100 cadenas predefinidas. Todas las cadenas contienen solo caracteres ASCII.

std::list<std::wstring> seeds{ L"google", L"yahoo", L"stackoverflow"};

Mi aplicación recibe constantemente muchas cadenas que pueden contener caracteres. Necesito verificar cada línea recibida y decidir si contiene semillas o no. La comparación debe ser insensible a mayúsculas y minúsculas.

Necesito el algoritmo más rápido posible para probar la cadena recibida.

En este momento mi aplicación usa este algo:

std::wstring testedStr; for (auto & seed : seeds) { if (boost::icontains(testedStr, seed)) { return true; } } return false;

Funciona bien, pero no estoy seguro de que esta sea la forma más eficiente.

¿Cómo es posible implementar el algoritmo para lograr un mejor rendimiento?

Esta es una aplicación de Windows. La aplicación recibe cadenas std::wstring válidas.

Actualizar

Para esta tarea implementé Aho-Corasick algo. Si alguien pudiera revisar mi código, sería genial, no tengo mucha experiencia con tales algoritmos. Enlace a la implementación: gist.github.com

Como una variante de la respuesta de DarioOO, podría obtener una implementación posiblemente más rápida de una coincidencia de expresión regular, al codificar un analizador lex para sus cadenas. Aunque normalmente se usa junto con yacc , este es un caso en el que lex por sí solo hace el trabajo, y los analizadores lex suelen ser muy eficientes.

Este enfoque podría fallar si todas sus cadenas son largas, ya que un algoritmo como Aho-Corasick , Commentz-Walter o Rabin-Karp probablemente ofrecería mejoras significativas, y dudo que las implementaciones de lex usen dicho algoritmo.

Este enfoque es más difícil si tiene que poder configurar las cadenas sin reconfiguración, pero dado que flex es de código abierto, puede canibalizar su código.

Debe probar una utilidad regex preexistente, puede ser más lenta que su algoritmo enrollado a mano, pero la expresión regular se trata de hacer coincidir múltiples posibilidades, por lo que es probable que sea varias veces más rápido que un hashmap o una simple comparación de todas las cadenas. Creo que las implementaciones de expresiones regulares ya pueden usar el algoritmo Aho-Corasick mencionado por RiaD, por lo que básicamente tendrá a su disposición una implementación bien probada y rápida.

Si tiene C ++ 11 ya tiene una biblioteca de expresiones regulares estándar

#include <string> #include <regex> int main(){ std::regex self_regex("google|yahoo|"); regex_match(input_string ,self_regex); }

Espero que esto genere el mejor árbol de coincidencias mínimas posible, así que espero que sea realmente rápido (¡y confiable!)

Editar: como señaló Matthieu M., el OP preguntó si una cadena contiene una palabra clave. Mi respuesta solo funciona cuando la cadena es igual a la palabra clave o si puede dividir la cadena, por ejemplo, por el carácter de espacio.

Especialmente con una gran cantidad de posibles candidatos y conocerlos en tiempo de compilación utilizando una función hash perfecta con una herramienta como gperf vale la pena intentarlo. El principio principal es que se siembra un generador con su semilla y se genera una función que contiene una función hash que no tiene colisiones para todos los valores semilla. En el tiempo de ejecución, le da a la función una cadena y calcula el hash y luego comprueba si es el único candidato posible que corresponde al hashvalue.

El costo de tiempo de ejecución es el hash de la cadena y luego se compara con el único candidato posible (O (1) para el tamaño de semilla y O (1) para la longitud de la cadena).

Para hacer que el caso de comparación no sea sensible, solo use tolower en la semilla y en su cadena.

Puedes usar el algoritmo Aho-Corasick

Construye trie / autómata donde algunos vértices marcados como terminales lo que significaría que la cadena tiene semillas.

Está construido en O(sum of dictionary word lengths) y da la respuesta en O(test string length)

Ventajas:

  • Funciona específicamente con varias palabras del diccionario y el tiempo de verificación no depende del número de palabras (si no consideramos casos en los que no se ajusta a la memoria, etc.)
  • El algoritmo no es difícil de implementar (al menos en comparación con las estructuras de sufijos)

Puede hacer que no distinga entre mayúsculas y minúsculas bajando cada símbolo si es ASCII (los caracteres no ASCII no coinciden de todos modos)

Si hay una cantidad finita de cadenas coincidentes, esto significa que puede construir un árbol de modo que, leído desde la raíz hasta las hojas, cadenas similares ocupen ramas similares.

Esto también se conoce como trie o árbol Radix .

Por ejemplo, podríamos tener las cadenas cat, coach, con, conch y dark, dad, dank, do . Su trie podría verse así:

Una búsqueda de una de las palabras en el árbol buscará el árbol, comenzando desde una raíz. Llegar a una hoja correspondería a una coincidencia con una semilla. En cualquier caso, cada personaje de la cadena debe coincidir con uno de sus hijos. Si no lo hace, puede finalizar la búsqueda (por ejemplo, no consideraría ninguna palabra que comience con "g" o cualquier palabra que comience con "cu").

Hay varios algoritmos para construir el árbol, así como buscarlo y modificarlo sobre la marcha, pero pensé que daría una descripción conceptual de la solución en lugar de una específica, ya que no conozco el mejor algoritmo para eso.

Conceptualmente, un algoritmo que podría usar para buscar en el árbol estaría relacionado con la idea detrás de una especie de radix de una cantidad fija de categorías o valores que un personaje en una cadena podría adoptar en un momento dado.

Esto le permite verificar una palabra en su word-list . Como está buscando esta lista de palabras como subcadenas de su cadena de entrada, habrá más que esto.

Editar: como se ha mencionado en otras respuestas, el algoritmo Aho-Corasick para la coincidencia de cadenas es un algoritmo sofisticado para realizar la coincidencia de cadenas, que consiste en un trie con enlaces adicionales para tomar "accesos directos" a través del árbol y tener un patrón de búsqueda diferente para acompañar esto. (Como nota interesante, Alfred Aho también es colaborador del popular libro de texto del compilador, Compiladores: principios, técnicas y herramientas , así como del libro de texto de algoritmos, El diseño y análisis de algoritmos informáticos . También es un ex miembro de Bell Labs. Margaret J. Corasick no parece tener demasiada información pública sobre sí misma.)