Qué algoritmo se puede utilizar para buscar duplicados de frases en una cadena?

Question

Dada una cadena arbitraria, lo que es un eficiente método de búsqueda de duplicados frases?Podemos decir que las frases deben ser de más de una cierta longitud para ser incluidos.

Idealmente, usted terminaría con el número de apariciones de cada frase.

Answer 1

Al igual que la anterior a la gente hablar de que el sufijo árbol es la mejor herramienta para el trabajo.Mi sitio favorito para árboles de sufijos es http://www.allisons.org/ll/AlgDS/Tree/Suffix/.Enumera todos los símbolos de los usos de los árboles de sufijos en una página y tiene una prueba de js aplicación integrada para la prueba de las cadenas y el trabajo a través de ejemplos.

Answer 2

En teoría

• Un sufijo de la matriz de es la "mejor" respuesta ya que puede ser implementado para el uso del espacio lineal y el tiempo para detectar duplicados subcadenas.Sin embargo, - el ingenuo aplicación realmente toma tiempo O(n^2 log n) para ordenar los sufijos, y no es completamente obvio cómo reducir esto a O(n log n), y mucho menos de O(n), aunque se pueden leer los papeles relacionados si lo deseas.
• Un sufijo de árbol puede tomar un poco más de memoria (todavía lineal, a pesar de que) de un sufijo de la matriz, pero es más fácil de implementar para construir rápidamente ya que se puede usar algo como un radix sort idea de como agregar cosas para el árbol (ver el enlace de wikipedia desde el nombre para más detalles).
• El Algoritmo KMP también es bueno ser consciente de que está especializado en la búsqueda de un determinado subcadena dentro de una cadena más larga muy rápidamente.Si sólo necesita de este caso especial, sólo tiene que utilizar KMP y no hay necesidad de molestarse en construir un índice de basta a la primera.

En la práctica

Supongo que estás analizando un documento de real del lenguaje natural (por ejemplo,Inglés) palabras, y que realmente quiere hacer algo con los datos que se recolectan.

En este caso, es posible que sólo quieren hacer una rápida n-gram el análisis de algunos de los pequeños de n, tal como se acaba de n=2 o 3.Por ejemplo, puede convertir el documento en una lista de palabras eliminando los signos de puntuación, uso de mayúsculas, y los derivados de las palabras (que se ejecuta, administra - > "ejecutar") para aumentar la semántica de los partidos.A continuación, construir un mapa hash (como hash_map en C++, un diccionario en python, etc) de cada par adyacente de palabras a su número de apariciones hasta ahora.En el extremo usted consigue algunos datos muy útiles que era muy rápido para el código, y no es una locura, lento para correr.

Answer 3

Sufijo de árboles son una buena manera de implementar esto.La parte inferior de este artículo ha enlaces a las implementaciones en diferentes idiomas.

Answer 4

Como jmah dijo, puede usar el sufijo árboles/sufijo de matrices para esto.

Hay una descripción de un algoritmo que podría utilizar aquí (véase la Sección 3.1).

Usted puede encontrar una descripción más a fondo en el libro se citan (Gusfield, 1997), que es en la búsqueda de libros de google.

Answer 5

suponga que se dan ordena Una matriz con n entradas (i=1,2,3,...,n)

Algo(A(i))
{
  while i<>n
  {
    temp=A[i];
    if A[i]<>A[i+1] then
    {     
      temp=A[i+1];
      i=i+1;
      Algo(A[i])
    }
    else if A[i]==A[i+1] then
      mark A[i] and A[i+1] as duplicates
  }
}

Esta algo pistas en O(n) tiempo.