Ayuda con búsqueda de palabra en txt

[ZedGe]

Necesito buscar 1 palabra en un .txt gigante 70.000 palabras, el problema es que al tener que buscar muchas palabras el tiempo es demasiado.

Mi código es algo así:

Código [Seleccionar] Expandir


for(int c = 0; c< largo;c++)
{
fd2 = open ( "abuscar.txt", O_RDWR);
string asd = arr[c];  //palabras a buscar
if ( fd2 < 0 ) //Si no se abre el archivo
    cout<<" El Archivo No se Pudo Abrir !!! ";

  while ( read ( fd2 , &L , 1 ) > 0 && aux2 == 0) //Leo carácter a caracter
      {
if(L == '\n') //Mientras no se lea la palabra del diccionario
{
if(asd.compare(palabra3) == 0) //Si esta se borra
{
aux++;
aux2=1;
arr[c] = " ";
}
palabra3.clear(); //Si no esta se deja
}
else //Si no esta formo un nuevo string
palabra3 = palabra3 + L;
} //Fin while
aux2=0;
close(fd2);
} //Fin for



Es solo parte del código para que vean como hago la comparación, hay alguna forma mas eficiente de hacerlo?





EDITO: Puede ser C o C++

[amchacon]

Busqueda binaria.

El algoritmo es sencillo, tienes que ordenar el diccionario alfabeticamente. Haces la comparación con el elemento medio, puede pasar tres cosas:

- Que sea la palabra que buscas.
- Que esté después de la palabra que buscas. Descartas la segunda mitad.
- Que esté antes de la palabra que buscas. Descartas la primera mitad.

Vuelves ha hacer lo mismo en las palabras que te queden hasta que la encuentres. En cada comparación estarás descartando la mitad de las palabras cada vez

Para hacer las comparaciones, puedes ayudarte de los operadores == y > de los strings.

PD: Por cierto, para leer una linea entera de un archivo tienes la función getline.

[ZedGe]

Muchas gracias, encontré por ahí el usar TRIE =D...

Y leo letra a letra por que necesito de alguna forma sacar algunos signos xd



Gracias lo intentare

[ghastlyX]

Si bien puedes utilizar estrategias tipo Trie, para el problema que planteas la manera más sencilla es la que te han comentado, leer primero todo el diccionario de palabras en el que buscas, ordenarlo y por cada palabra que busques hacer una búsqueda binaria. A la hora de implementarlo, lo más sencillo es que metas dichas palabras en un set de C++ y utilices la función count o find para saber si están o no.

Si optaras por utilizar estructuras tipo Trie, lo más eficiente sería utilizar o bien una estrategia de preprocesado del texto vía Suffix Tree (muy difícil de implementar siendo eficiente) o bien preprocesar los patrones a buscar vía Aho-Corasick (algo menos difícil que un Suffix Tree a mi opinión, pero también muy difícil). Sinceramente el tiempo de ejecución que vas a ganar con estas opciones para un diccionario de 70000 palabras es bastante despreciable, así que yo optaría por la binaria, que con un set son 5 líneas.

[eferion]

Si bien puedes utilizar estrategias tipo Trie, para el problema que planteas la manera más sencilla es la que te han comentado, leer primero todo el diccionario de palabras en el que buscas, ordenarlo y por cada palabra que busques hacer una búsqueda binaria. A la hora de implementarlo, lo más sencillo es que metas dichas palabras en un set de C++ y utilices la función count o find para saber si están o no.

Si optaras por utilizar estructuras tipo Trie, lo más eficiente sería utilizar o bien una estrategia de preprocesado del texto vía Suffix Tree (muy difícil de implementar siendo eficiente) o bien preprocesar los patrones a buscar vía Aho-Corasick (algo menos difícil que un Suffix Tree a mi opinión, pero también muy difícil). Sinceramente el tiempo de ejecución que vas a ganar con estas opciones para un diccionario de 70000 palabras es bastante despreciable, así que yo optaría por la binaria, que con un set son 5 líneas.

Falta decir que con set no hace falta ordenar las palabras previamente ya que set, por definición, es una lista ordenada.