Estructura de datos más rápida para buscar una cadena

Question

Tengo este código que determina si una palabra (ignorando el caso) se incluye en un archivo de texto wordList. Sin embargo, el archivo de texto wordList puede tener 65000 ++ líneas, y simplemente buscar una palabra usando mi implementación a continuación toma casi un minuto. ¿Podrías pensar en alguna mejor implementación?

Gracias!

import java.io.*; 
import java.util.*; 

public class WordSearch 
{ 
    LinkedList<String> lxx; 
    FileReader fxx; 
    BufferedReader bxx; 

    public WordSearch(String wordlist) 
     throws IOException 
    { 
     fxx = new FileReader(wordlist); 
     bxx = new BufferedReader(fxx); 
     lxx = new LinkedList<String>(); 
     String word; 

     while ((word = bxx.readLine()) != null) 
      { 
      lxx.add(word); 
     } 

     bxx.close(); 
    } 

    public boolean inTheList (String theWord) 
    { 
     for(int i =0 ; i < lxx.size(); i++) 
      { 
      if (theWord.compareToIgnoreCase(lxx.get(i)) == 0) 
        { 
       return true; 
      } 
     } 

     return false; 
    } 
} 

Answer 1

Use un HashSet en el que pone una versión en minúscula de cada palabra. Comprobar si un HashSet contiene una cadena especificada es, en promedio, una operación de tiempo constante (leer: extremadamente rápido).

Answer 2

Dado que usted está buscando, es posible que desee considerar la clasificación de la lista antes de la búsqueda; entonces puedes hacer una búsqueda binaria que es mucho más rápida que la búsqueda lineal. Eso puede ayudar si realiza múltiples búsquedas en la misma lista, de lo contrario, la multa que paga por ordenar la lista no vale la pena para buscar solo una vez.

Además, hacer una búsqueda lineal en una lista vinculada utilizando "lxx.get (i)" es una tarea problemática. LinkedList.get() es O (n). Puede usar un iterador (manera fácil: para (String s: lxx)) o cambiar a un tipo de lista que tiene O (1) tiempo de acceso, como ArrayList.

Answer 3

Cada búsqueda a través de l en una operación O (n), por lo que esto será bastante costoso cuando tenga miles de palabras. En su lugar, utilice un HashSet:

Set<String> lxx; 

... 

lxx = new HashSet<String>(); 
while ((word = bxx.readLine()) != null) { 
     lxx.add(word.toLowerCase()); 
} 
bxx.close(); 

y luego usar lxx.contains(theWord.toLowerCase()) para comprobar si la palabra está en el archivo. Cada búsqueda en el HashSet es una operación O (1), por lo que los tiempos que toma son (casi) independientes del tamaño de su archivo.

Answer 4

En primer lugar, no declara la variable de ser un LinkedList, os lo anunciará a ser una lista (partes del código no se refiere a la lista de borrado:

public class WordSearch 
{ 
    List<String> lxx; 

    public WordSearch(String wordlist) 
     throws IOException 
    { 
     lxx = new LinkedList<String>(); 
    } 
} 

Lo siguiente no llame subir la lista, utilizando un encuentro ListaEnlazada será muy lento en lugar de utilizar un iterador ... mejor aún utilizar el nuevo stype de bucle que utiliza un iterador para usted:.

public boolean inTheList (String theWord) 
    { 
     for(String word : lxx) 
     { 
      if (theWord.compareToIgnoreCase(word) == 0) 
      { 
       return true; 
      } 
     } 

     return false; 
    } 

próximo cambio de la nueva lista enlazada a un nuevo ArrayList :

lxx = new ArrayList();

Este código debe ser más rápido, pero aún puede hacerlo mejor.

Dado que no le importan las palabras duplicadas, use Set en lugar de una lista y use un HashSet en lugar de una ArrayList.

Hacer eso acelerará el programa significativamente.

Su código original, al utilizar LinkedList con get, tiene que volver a empezar al principio de la lista cada vez que busca la siguiente palabra en la lista. Usar el iterador (a través del nuevo estilo para cada bucle) evita que eso suceda.

El uso de una lista enlazada significa que cada vez que tiene que ir a la siguiente palabra de la lista hay una búsqueda involucrada, ArrayList no tiene esa sobrecarga.

El uso de un HashSet termina (probablemente) usando una estructura de árbol que tiene búsquedas muy rápidas.

Answer 5

Aquí está mi implementación buscando menos de 50 ms.

Primero tiene que cargar el archivo y mantenerlo ordenado en la memoria.

Puedes cargarlo como quieras, pero si lo cargas en trozos grandes será más fácil.

Mi entrada fue el byte into python book (descargado la versión de un solo archivo HTML) y la Java language specification (descargado el html y crear un único archivo de todas las páginas html)

Para crear la lista en un archivo grande Solía este mismo programa (ver código comentado).

Una vez que tengo un gran archivo con cerca de 300 mil palabras, me encontré con el programa con esta salida:

C:\Users\oreyes\langs\java\search>dir singlelineInput.txt 
El volumen de la unidad C no tiene etiqueta. 
El número de serie del volumen es: 22A8-203B 

Directorio de C:\Users\oreyes\langs\java\search 

04/03/2011 09:37 p.m.   3,898,345 singlelineInput.txt 
       1 archivos  3,898,345 bytes 

C:\Users\oreyes\langs\java\search>javac WordSearch.java 

C:\Users\oreyes\langs\java\search>java WordSearch singlelineInput.txt "great" 
Loaded 377381 words in 2844 ms 
true 
in 31 ms 

C:\Users\oreyes\langs\java\search>java WordSearch singlelineInput.txt "great" 
Loaded 377381 words in 2812 ms 
true 
in 31 ms 

C:\Users\oreyes\langs\java\search>java WordSearch singlelineInput.txt "awesome" 
Loaded 377381 words in 2813 ms 
false 
in 47 ms 

C:\Users\oreyes\langs\java\search>gvim singlelineInput.txt 

C:\Users\oreyes\langs\java\search>java WordSearch singlelineInput.txt "during" 
Loaded 377381 words in 2813 ms 
true 
in 15 ms 

C:\Users\oreyes\langs\java\search>java WordSearch singlelineInput.txt "specification" 
Loaded 377381 words in 2875 ms 
true 
in 47 ms 

C:\Users\oreyes\langs\java\search>java WordSearch singlelineInput.txt "<href" 
Loaded 377381 words in 2844 ms 
false 
in 47 ms 

C:\Users\oreyes\langs\java\search>java WordSearch singlelineInput.txt "<br>" 
Loaded 377381 words in 2829 ms 
true 
in 15 ms 

siempre menores de 50 ms.

Aquí está el código:

import java.io.*; 
    import java.util.*; 

    class WordSearch { 
     String inputFile; 
     List<String> words; 
     public WordSearch(String file) { 
      inputFile = file; 
     } 
     public void initialize() throws IOException { 
      long start = System.currentTimeMillis(); 
      File file = new File(inputFile); 
      ByteArrayOutputStream baos = new ByteArrayOutputStream((int) file.length()); 
      FileInputStream in = new FileInputStream(file); 
      copyLarge(in, baos, (int)file.length()); 

      Scanner scanner = new Scanner(new ByteArrayInputStream( baos.toByteArray())); 
      words = new LinkedList<String>(); 
      while(scanner.hasNextLine()) { 
       String l = scanner.nextLine().trim(); 
       //for(String s : l.split("\\s+")){ 
       //System.out.println(s); 
       words.add(l.toLowerCase()); 
       //} 
      } 

      Collections.sort(words); 
      for(String s : words) { 
       //System.out.println(s); 
      } 
      System.out.println("Loaded " + words.size() + " words in "+ (System.currentTimeMillis() - start) + " ms" ); 
     } 

     public boolean contains(String aWord) { 
      return words.contains(aWord.toLowerCase()); 
     } 
     // taken from: http://stackoverflow.com/questions/326390/how-to-create-a-java-string-from-the-contents-of-a-file/326413#326413 
     public static long copyLarge(InputStream input, OutputStream output, int size) 
       throws IOException { 
      byte[] buffer = new byte[size];// something biggie 
      long count = 0; 
      int n = 0; 
      while (-1 != (n = input.read(buffer))) { 
       output.write(buffer, 0, n); 
       count += n; 
      } 
      return count; 
     } 
     public static void main(String ... args) throws IOException { 
      WordSearch ws = new WordSearch(args[0]); 
      ws.initialize(); 
      long start = System.currentTimeMillis(); 
      System.out.println(ws.contains(args[1])); 
      System.out.println("in "+ (System.currentTimeMillis() - start) +" ms "); 

     } 
    } 

La parte difícil era conseguir una entrada de la muestra: P

Answer 6

adivina que, utilizando un HashMap retornos en ningún momento:

Aquí está la versión modificada y termina siempre en 0 ms.

import java.io.*; 
    import java.util.*; 

    class WordSearch { 
     String inputFile; 
     //List<String> words; 
     Set<String> words; 
     public WordSearch(String file) { 
      inputFile = file; 
     } 
     public void initialize() throws IOException { 
      long start = System.currentTimeMillis(); 
      File file = new File(inputFile); 
      ByteArrayOutputStream baos = new ByteArrayOutputStream((int) file.length()); 
      FileInputStream in = new FileInputStream(file); 
      copyLarge(in, baos, (int)file.length()); 

      Scanner scanner = new Scanner(new ByteArrayInputStream( baos.toByteArray())); 
      words = new HashSet<String>(); 
      while(scanner.hasNextLine()) { 
       String l = scanner.nextLine().trim(); 
       //for(String s : l.split("\\s+")){ 
       //System.out.println(s); 
       words.add(l.toLowerCase()); 
       //} 
      } 

      //Collections.sort(words); 
      for(String s : words) { 
       System.out.println(s); 
      } 
      System.out.println("Loaded " + words.size() + " words in "+ (System.currentTimeMillis() - start) + " ms" ); 
     } 

     public boolean contains(String aWord) { 
      return words.contains(aWord.toLowerCase()); 
     } 

     public static long copyLarge(InputStream input, OutputStream output, int size) 
       throws IOException { 
      byte[] buffer = new byte[size];// something biggie 
      long count = 0; 
      int n = 0; 
      while (-1 != (n = input.read(buffer))) { 
       output.write(buffer, 0, n); 
       count += n; 
      } 
      return count; 
     } 
     public static void main(String ... args) throws IOException { 
      WordSearch ws = new WordSearch(args[0]); 
      ws.initialize(); 
      long start = System.currentTimeMillis(); 
      System.out.println(ws.contains(args[1])); 
      System.out.println("in "+ (System.currentTimeMillis() - start) +" ms "); 

     } 
    } 

Ahora sé a ciencia cierta :)

Answer 7

dos sugerencias: Ambas estructuras de datos que dan un mejor rendimiento.

1. Directed gráfico palabra acíclico (DAWG)
2. estructura de datos de diccionario. n-tree