4

Estou a procura de uma lógica onde eu possa encontrar em uma quantidade exorbitante de dados, frases que sejam comuns. Frase nesse contexto é sequencia de palavras.

Por exemplo nestas orações:

  • Estou a viajar para Orlando do Sul
  • Queria muito ir para Orlando do Sul
  • O dia está lindo aqui em Orlando do Sul

A frase, ou sequencia de palavras em comum seria Orlando do Sul

pesquisando eu encontrei essa pergunta no StackOverflow EN entretando não consegui compreender a resposta.

9
  • Trata-se de un array de palavras, ou elas estão todas numa mesma variável? As palavras estão embaralhadas ou são grupos de frases? Commented 7/05/2016 às 15:15
  • @AdrianoLuz a princípio é uma string de palavras, ou como disse elas estão todas numa mesma variável em forma de texto.
    – Elaine
    Commented 7/05/2016 às 15:17
  • Existe um delimitador entre as frases, como um ponto final ou um traço? Commented 7/05/2016 às 15:27
  • @AdrianoLuz teoricamente deve-se considerar mas por ser conteúdo aleatório de usuários não pode-se basear nisso como principal pilar.
    – Elaine
    Commented 7/05/2016 às 15:30
  • A resposta fala a respeito do uso de dicionario, bom foi o que eu entendi, uma maneira de atribuir um inteiro a palavra escolhida assim poderia fazer as comparações e também ordenar o array de palavras e armazena-las para ser usado com outras listas, entretanto, não sei se aquela resposta te da a solução.
    – gato
    Commented 7/05/2016 às 23:29

1 Resposta 1

6

Você não menciona exatamente o que você não entendeu na resposta do SOEN. Mas uma coisa que o autor lá repete bastante é "tempo linear". A ideia de um algoritmo capaz de processar os dados em tempo linear é que o tempo que ele demora para processar cresce linearmente com a quantidade de dados de entrada. Pense idealmente em uma proporção direta: quanto mais dados, mais tempo leva. É o esperado para um algoritmo suficientemente bom. Por outro lado, um algoritmo ruim levaria tempo exponencial para processar os dados. Assim, quanto mais dados, muitíssimo mais tempo ele levaria para processar - a ponto de se tornar inviável para uma quantidade de dados que nem precisa ser "exorbitante".

Pra entender melhor esse conceito, sugiro essa outra questão e também essa outra questão.

Bom, você tem muitos dados (as palavras ou os caracteres a processar), então precisa se preocupar com o desempenho do seu algoritmo. A resposta do SOEN sugere uma abordagem baseada em alguns algoritmos que eu desconheço, mas pelo que eu pude entender a ideia essencial é varrer os dados (em tempo linear) e montar uma árvore de sufixos (armazenada em uma matriz): essa árvore é uma estrutura de dados supostamente importante (e famosa) na análise de texto que contém todos os possiveis sufixos (terminações) de uma string. O exemplo do link da Wikipedia é a palavra "BANANA", que pode ter o sufixo "ANANA", ou o sufixo "NANA" e assim por diante (o $ significa o fim da palavra):

inserir a descrição da imagem aqui

Aparentemente, utilizando estruturas como essa você é capaz de construir também a árvore de prefixos (todos os prefixos possíveis para o seu texto, considerado como uma string só) e então encontrar nela os prefixos mais longos e mais comuns.

Os conceitos envolvidos não parecem ser tão complexos, mas vai requerer que você leia e estude-os provavelmente em inglês. O artigo da Wikipedia pode ser insuficiente, mas talvez vc encontre mais material procurando por "árvore de sufixos".

2
  • Obrigada, você explanou muito, só não entendo como essa forma me leva ao que eu desejo...
    – Elaine
    Commented 8/05/2016 às 3:16
  • A minha intuição e experiência me dizem que essa estrutura vai mesmo ser muito útil pra você porque é uma boa forma de organizar o conteúdo do texto, talvez para permitir acumular alguma contagem a respeito de repetições. Mas, como eu disse, eu não entendo muito desses algoritmos, então não tenho como preparar uma resposta que seja realmente muito didática. Infelizmente vc vai ter que estudar por conta própria ou esperar alguém que realmente conheça do assunto postar uma resposta mais palatável. As dicas que eu te passei são um bom ponto de partida para os seus estudos. Boa sorte. :) Commented 8/05/2016 às 4:38

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .