algorithm - español - ¿Qué algoritmo puedes usar para encontrar frases duplicadas en una cadena?

algoritmo fonetico español

Question

Dada una cadena arbitraria, ¿cuál es un método eficiente para encontrar frases duplicadas? Podemos decir que las frases deben ser más largas que una cierta duración para ser incluidas.

Idealmente, terminarías con el número de apariciones para cada frase.

Answer 1

Como dijo jmah, puedes usar matrices de sufijo / matrices de sufijos para esto.

Hay una descripción de un algoritmo que puede usar aquí (consulte la Sección 3.1).

Puede encontrar una descripción más detallada en el libro que ellos citan (Gusfield, 1997), que está en los libros de google .

Answer 2

Los sufijos son una buena forma de implementar esto. La parte inferior de ese artículo tiene enlaces a implementaciones en diferentes idiomas.

Answer 3

En teoria

• Una matriz de sufijos es la "mejor" respuesta, ya que se puede implementar para utilizar el espacio y el tiempo lineal para detectar cualquier subcadena duplicada. Sin embargo, la implementación ingenua 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 a O (n), aunque puede leer los documentos relacionados si lo desea.
• Sin embargo, un árbol de sufijo puede llevar un poco más de memoria (aún lineal) que una matriz de sufijo, pero es más fácil de implementar para compilar rápidamente, ya que puede usar algo como una idea de ordenamiento radical al agregar cosas al árbol (consulte el enlace de wikipedia el nombre para más detalles).
• También es bueno tener en cuenta el algoritmo KMP , que está especializado para buscar una subcadena particular dentro de una cadena más larga muy rápidamente. Si solo necesita este caso especial, simplemente use KMP y no necesita molestarse en crear un índice de suficientes primero.

En la práctica

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

En este caso, es posible que desee realizar un análisis n-grama rápido para una n pequeña, como por ejemplo n = 2 o 3. Por ejemplo, puede poner en el token el documento en una lista de palabras eliminando la puntuación, las mayúsculas, y palabras derivadas (en ejecución, ejecuta ambos -> ''ejecutar'') para aumentar las coincidencias semánticas. Luego, simplemente construya un mapa hash (como hash_map en C ++, un diccionario en python, etc.) de cada par de palabras adyacentes hasta su cantidad de ocurrencias hasta el momento. Al final, obtienes datos muy útiles que fueron muy rápidos de codificar, y no raros de ejecutar.

Answer 4

supongamos que se le asigna una matriz ordenada A 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
  }
}

Este algo se ejecuta en O (n) tiempo.

Answer 5

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