Mejor algoritmo para indexar oraciones

Question

Imagine que tengo una situación en la que necesito indizar oraciones. Déjame explicarlo un poco más profundo.

Por ejemplo, tengo estas frases:

1. El hermoso cielo.
2. Beautiful sky dream.
3. Hermoso sueño.

Por lo que yo puedo imaginar el índice debería ser algo como esto:

alt text http://img7.imageshack.us/img7/4029/indexarb.png

Pero también me gustaría hacer una búsqueda por cualquiera de estas palabras.

Por ejemplo, si busco por "the" Debería mostrarme la conexión a "beautiful". si busco por "bello" debería darme las conexiones a (anterior) "The", (next) "sky" y "dream". Si busco por "cielo" debería dar una conexión (anterior) a "bella" y etc ...

¿Alguna idea? ¿Quizás ya conozcas el algoritmo existente para este tipo de problema?

Answer 1

Este oughta le acercarán, en C#:

class Program 
{ 
    public class Node 
    { 
     private string _term; 
     private Dictionary<string, KeyValuePair<Node, Node>> _related = new Dictionary<string, KeyValuePair<Node, Node>>(); 

     public Node(string term) 
     { 
      _term = term; 
     } 

     public void Add(string phrase, Node previous, string [] phraseRemainder, Dictionary<string,Node> existing) 
     { 
      Node next= null; 
      if (phraseRemainder.Length > 0) 
      { 
       if (!existing.TryGetValue(phraseRemainder[0], out next)) 
       { 
        existing[phraseRemainder[0]] = next = new Node(phraseRemainder[0]); 
       } 
       next.Add(phrase, this, phraseRemainder.Skip(1).ToArray(), existing); 
      } 
      _related.Add(phrase, new KeyValuePair<Node, Node>(previous, next)); 

     } 
    } 


    static void Main(string[] args) 
    { 
     string [] sentences = 
      new string [] { 
       "The beautiful sky", 
       "Beautiful sky dream", 
       "beautiful dream" 
      }; 

     Dictionary<string, Node> parsedSentences = new Dictionary<string,Node>(); 

     foreach(string sentence in sentences) 
     { 
      string [] words = sentence.ToLowerInvariant().Split(' '); 
      Node startNode; 
      if (!parsedSentences.TryGetValue(words[0],out startNode)) 
      { 
       parsedSentences[words[0]] = startNode = new Node(words[0]); 
      } 
      if (words.Length > 1) 
       startNode.Add(sentence,null,words.Skip(1).ToArray(),parsedSentences); 
     } 
    } 
} 

he tomado la libertad de asumir que quería conservar la frase inicial en sí. Al final de esto, tendrá una lista de palabras en las frases, y en cada una, una lista de frases que usan esa palabra, con referencias a las palabras siguientes y anteriores en cada frase.

Answer 2

árbol algoritmos de búsqueda (como BST, ect)

Answer 3

Usando un associative array le permitirá analizar sintácticamente rápidamente oraciones en Perl. Es mucho más rápido de lo que anticiparía y puede ser efectivamente arrojado en una estructura similar a un árbol para su posterior uso por un lenguaje de nivel superior.

Answer 4

Puede probar y profundizar en Markov chains, formado a partir de palabras de oraciones. También necesitará una cadena bidireccional (es decir, para encontrar las palabras siguientes y anteriores), es decir, almacenar las palabras probables que aparezcan justo después de la anterior o anterior.

Por supuesto, la cadena de Markov es un proceso estocástico para generar contenido, sin embargo, se puede usar un enfoque similar para almacenar la información que necesita.

Answer 5

Eso parece que podría ser almacenada en una base de datos muy simple con las siguientes tablas:

Words: 
    Id  integer primary-key 
    Word varchar(20) 
Following: 
    WordId1 integer foreign-key Words(Id) indexed 
    WordId2 integer foreign-key Words(Id) indexed 

Entonces, cada vez que analizar una frase, basta con insertar los que no están ya allí, de la siguiente manera:

The beautiful sky. 
    Words (1,'the') 
    Words (2, 'beautiful') 
    Words (3,, 'sky') 
    Following (1, 2) 
    Following (2, 3) 
Beautiful sky dream. 
    Words (4, 'dream') 
    Following (3, 4) 
Beautiful dream. 
    Following (2, 4) 

Luego puede consultar al contenido de su corazón sobre qué palabras siguen o preceden a otras palabras.

Answer 6

respuesta Corto

Crear una estructura con dos vectores de enlaces anteriores/adelante. A continuación, almacene las estructuras de palabras en una tabla hash con la clave como la palabra misma.

Respuesta larga

Se trata de un problema de análisis lingüístico que no se resuelve fácilmente, a menos que no le importe galimatías.

1. Fui a la cancha de baloncesto del parque.
2. ¿Estacionarías el automóvil?

Su algoritmo de vinculación creará frases como:

1. Fui al parque del coche.
2. ¿Estacionarías una cancha de baloncesto?

No estoy muy seguro de las aplicaciones de SEO de esto, pero no me gustaría recibir otro sitio de spam que tome un resultado de búsqueda.

Answer 7

Imagino que querrías algún tipo de estructura Inverted index. Tendría un Hashmap con las palabras como teclas que apuntan a listas de pares del formulario (sentence_id, position). A continuación, almacena tus oraciones como matrices o listas vinculadas. Su ejemplo sería este:

sentence[0] = ['the','beautiful', 'sky']; 
sentence[1] = ['beautiful','sky', 'dream']; 
sentence[2] = ['beautiful', 'dream']; 

inverted_index = 
{ 
'the': {(0,0)}, 
'beautiful': {(0,1), (1,0), (2,0)}, 
'sky' : {(0,2),(1,1)}, 
'dream':{(1,2), (2,1)} 
}; 

Al usar esta estructura, las búsquedas de palabras se pueden realizar en tiempo constante. Después de haber identificado la palabra que desea, encontrar la palabra anterior y posterior en una oración dada también se puede hacer en tiempo constante.

Espero que esto ayude.