O algoritmo que você pode usar para encontrar frases duplicados em uma string?

Question

Dada uma seqüência arbitrária, o que é um método eficiente de encontrar frases duplicados? Podemos dizer que as frases devem ser superiores a um determinado comprimento para ser incluído.

O ideal seria acabar com o número de ocorrências para cada frase.

Answer 1

Como os povos anteriores mencionar que árvores de sufixos é a melhor ferramenta para o trabalho. Meu site favorito para árvores de sufixo é http://www.allisons.org/ll/ AlgDS / árvore / Sufixo / . Ele enumera todos os usos bacana de árvores de sufixo em uma página e tem um applicaton teste js incorporado para cordas de teste e de trabalho através de exemplos.

Answer 2

Em teoria

• A sufixo variedade é o 'melhor' resposta, uma vez que pode ser implementado para usar o espaço linear e tempo para detectar eventuais substrings duplicados. No entanto - a implementação ingênua, na verdade, leva tempo O (n ^ 2 log n) para classificar os sufixos, e não é completamente óbvia como reduzir esse baixo para O (n log n), e muito menos O (n), embora você pode ler os papéis relacionados se você quiser.
• A sufixo árvore pode levar um pouco mais de memória (ainda linear , embora) de uma matriz sufixo, mas é mais fácil de implementar para construir rapidamente desde que você pode usar algo como uma idéia radix tipo como você adicionar coisas à árvore (veja o link wikipedia do nome para detalhes).
• O KMP algoritmo também é bom para ser de consciência, que é especializada para a busca de uma substring particular dentro de uma cadeia mais longa muito rapidamente. Se você só precisa este caso especial, é só usar KMP e não precisa se preocupar construção de um índice de sufixos em primeiro lugar.

Na prática

Eu estou supondo que você está analisando um documento de linguagem natural real (por exemplo, Inglês) palavras, e você realmente quer fazer algo com os dados coletados.

Neste caso, você pode apenas querer fazer uma rápida análise href="http://en.wikipedia.org/wiki/N-gram" rel="noreferrer"> n-gram por algum pequeno n, tais como apenas n = 2 ou 3. por exemplo, você poderia tokenizar o documento em uma lista de palavras descascando para fora pontuação, letras maiúsculas e decorrentes palavras (corrida, corre tanto -> 'run') para aumento jogos semânticos. Em seguida, basta construir um mapa de hash (tais como hash_map em C ++, um dicionário no pitão, etc.) de cada par adjacente de palavras ao seu número de ocorrências até agora. No final, você obter alguns dados muito úteis que foi muito rápido ao código, e não louco lento para ser executado.

Answer 3

Sufixo árvores são uma boa maneira de implementar isso. A parte inferior do mesmo artigo tem links para implementações em diferentes idiomas.

Answer 4

Como JMAH disse, você pode usar árvores de sufixo / arranjos de sufixos para isso.

Há uma descrição de um algoritmo que você poderia usar aqui (ver Secção 3.1 ).

Você pode encontrar uma descrição mais detalhada no livro eles citam (Gusfield, 1997), que é no Google livros .

Answer 5

suponha que você está dado array ordenado A com 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
  }
}

A Algo é executado em O (n) de tempo.