elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Security Series.XSS. [Cross Site Scripting]


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Ayuda con búsqueda de palabra en txt
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Ayuda con búsqueda de palabra en txt  (Leído 2,130 veces)
ZedGe

Desconectado Desconectado

Mensajes: 154


Ver Perfil
Ayuda con búsqueda de palabra en txt
« en: 1 Septiembre 2013, 01:46 am »

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:
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++



« Última modificación: 1 Septiembre 2013, 01:50 am por ZedGe » En línea

amchacon


Desconectado Desconectado

Mensajes: 1.211



Ver Perfil
Re: Ayuda con búsqueda de palabra en txt
« Respuesta #1 en: 1 Septiembre 2013, 13:11 pm »

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.


En línea

Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar
ZedGe

Desconectado Desconectado

Mensajes: 154


Ver Perfil
Re: Ayuda con búsqueda de palabra en txt
« Respuesta #2 en: 2 Septiembre 2013, 07:13 am »

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
En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Ayuda con búsqueda de palabra en txt
« Respuesta #3 en: 2 Septiembre 2013, 11:55 am »

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.
En línea

eferion


Desconectado Desconectado

Mensajes: 1.248


Ver Perfil
Re: Ayuda con búsqueda de palabra en txt
« Respuesta #4 en: 2 Septiembre 2013, 11:58 am »

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.
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Ayuda con Seleccionar Palabra por Palabra
Programación Visual Basic
RickJack 6 4,610 Último mensaje 15 Septiembre 2008, 23:47 pm
por RickJack
[Batch] Ayuda con If (repetir palabra, no letra) « 1 2 »
Scripting
Geormarsch 15 7,971 Último mensaje 14 Octubre 2011, 19:55 pm
por Geormarsch
Duda sobre seleccionar palabra por palabra en RichTextBox (vb.net)
.NET (C#, VB.NET, ASP)
Susoch 3 5,026 Último mensaje 19 Enero 2012, 18:15 pm
por Susoch
insertar palabra por palabra a una matriz
Programación C/C++
Fabi0lo 3 2,458 Último mensaje 20 Octubre 2012, 18:17 pm
por rir3760
Conseguir todos los resultados de la búsqueda de una palabra en un archivo
PHP
SCM 1 774 Último mensaje 27 Febrero 2013, 02:10 am
por it3r
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines