Mejor estructura de datos en C++ para encontrar una cadena en un diccionario

Question

Soy un principiante de C++. ¿Puede alguien decirme la mejor estructura de datos en C++ para almacenar todas las palabras en un diccionario y encontrar si hay una palabra en el diccionario? Sé que las tablas hash son las mejores, pero no sé qué estructura de datos las usa.

Muchas gracias de antemano.

Answer 1

La biblioteca estándar de su implementación en C++ puede tener unordered_set o hash_set. Ellos son esencialmente lo mismo; el primero es parte del próximo estándar C++ 0x y es compatible con algunos de los últimos compiladores, el último es del SGI STL original y se incluye en muchas implementaciones de bibliotecas estándar.

Answer 2

hash_map, si lo tiene en la biblioteca del compilador de C++ (por ejemplo, GNU C++ o Microsoft Visual C++). Si está utilizando algún otro compilador menos extendido, sospecho que puede encontrar una implementación decente de terceros de hash_map de todos modos.

El próximo estándar de C++ llama a esta misma estructura de datos std::unordered_map.

Si no desea asociar ninguna información con palabras en su diccionario, simplemente registre si hay una palabra presente o no, puede usar las variaciones _set (en lugar de _map) de la estructura de datos anterior escribir nombres

Por supuesto, todas son plantillas (como todos los contenedores en la biblioteca estándar de C++), por lo que deberá crear instancias apropiadas con la sintaxis típica de la plantilla.

Answer 3

Si el único requisito es decidir si una palabra está contenida en un diccionario que nunca cambia, sin necesidad de otro tipo de información sobre la palabra (por ejemplo, un corrector ortográfico), entonces Bloom filter es un eficiente estructura de datos para esta tarea.

Si hay otros datos para asociar con cada palabra que debe buscarse, std::map es un buen punto de partida de propósito general.

Si se necesita autocompletar (cuando se ha ingresado una palabra parcial), se puede usar un Prefix tree (trie).

Answer 4

hashes son bastante buenos, pero la mejor estructura es trie. Puede obtener un trie de <ext/pb_ds/assoc_container.hpp> en GCC. Ver the online reference.

#include <ext/pb_ds/assoc_container.hpp> 
#include <string> 
#include <iostream> 

int main() { 
     pb_ds::trie< std::string, int > dict; 

     dict.insert(std::make_pair("hello", 3)); 

     std::cerr << (dict.find("hello") != dict.end()) << std::endl; 
     std::cerr << (dict.find("goodbye") != dict.end()) << std::endl; 
} 

Sólo map funcionalidad -como, no una pura set, se proporciona. En la muestra anterior agregué un dummy int como datos para mapear a ... realmente no debería doler mucho.

Lo que duele es que esto no funcionará fuera de GCC.

Por otro lado, una tabla hash -standard no (no std:: o ext:: nada) le permitiría sólo para encontrar coincidencias aproximadas, es decir, a buscar entre las sumas de comprobación de palabras en lugar de las palabras mismas. Esa sería la solución más rápida y compacta. Los diccionarios basados ​​en Bloom filters pueden contener muchos miles de palabras en algunos kilobytes.

Answer 5

Si está dispuesto a rodar su propia solución y su diccionario es fijo, un perfect hash es un buen camino a seguir. Garantiza un tiempo de búsqueda constante.

Answer 6

Yo preferiría usar un Trie. A Trie será una buena estructura de datos para construir un diccionario de memoria eficiente con búsquedas rápidas, y sí, autocompletado.

Piense en ello como una tabla hash, proporcionando una búsqueda rápida de pares clave-valor (o solo búsqueda de claves), pero a diferencia de una tabla hash, le permite iterar sobre las claves en orden ordenado.

Consulte Trie - Wiki para obtener más información/referencia.