Лучший алгоритм для индексирования предложений

Question

Представьте, что у меня есть ситуация, когда мне нужно индексировать предложения. Позвольте мне объяснить это немного глубже.

Например, у меня есть эти предложения:

1. Красивое небо.
2. Красивое небо мечты.
3. Красивая мечта.

Насколько я могу себе представить, индекс должен выглядеть следующим образом:

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

Но я также хотел бы сделать поиск по любому из этих слов.

Например, если я выполняю поиск по «значению», он должен показать мне подключение к «красивому». Если я ищу «прекрасный», он должен дать мне связи с (предыдущим) «The», (далее) «небо» и «сон». Если я ищу «небо», он должен дать (предыдущее) подключение к «красивому» и т. Д.

Любые идеи? Может быть, вы знаете уже существующий алгоритм для такого рода проблем?

Answer 1

Это Oughta получить закрытия, в 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); 
     } 
    } 
} 

Я взял на себя смелость, предполагая, что вы хотели, чтобы сохранить фактическую начальную фразу. В конце этого вы будете иметь список слов в фразах, а в каждом - список фраз, которые используют это слово, со ссылками на следующие и предыдущие слова в каждой фразе.

Answer 2

дерева Алгоритмы поиска (как BST, т.д.)

Answer 3

с использованием associative array позволит вам быстро проанализировать предложения в Perl. Это намного быстрее, чем вы ожидали, и его можно эффективно сбрасывать в дереве, подобном структуре, для последующего использования языком более высокого уровня.

Answer 4

Вы можете попробовать и вникать в Markov chains, образованный по словам предложений. Также вам понадобится цепочка из двух сторон (например, найти следующее и предыдущие слова), т. Е. Сохранить вероятные слова, которые появляются сразу после данного или непосредственно перед ним.

Конечно, цепь Маркова - это стохастический процесс для создания контента, однако подобный подход может использоваться для хранения необходимой вам информации.

Answer 5

Это выглядит, как он может быть сохранен в очень простую базу данных со следующими таблицами:

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

Затем, когда вы разбираете предложение, просто вставить те, которые уже не существуют, а именно:

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) 

Тогда вы можете запросить в своем сердце контент о том, какие слова следуют или предшествуют другим словам.

Answer 6

Короткий ответ

Создать-структуру с двумя векторами предыдущих вперед/ссылки. Затем сохраните слово structs в хэш-таблице с ключом как само слово.

Длинный ответ

Это языковая проблема разбора, не легко решить, если вы не возражаете тарабарщину.

1. Я пошел в парк баскетбольной площадки.
2. Вы бы припарковали машину.

Ваш алгоритм сшивание будет создавать предложения, как:

1. Я пошел в парк автомобиля.
2. Будете ли вы парковать баскетбольную площадку.

Я не совсем уверен в SEO-приложениях этого, но я не хотел бы, чтобы другой таинственный сайт спам занимался поиском.

Answer 7

Я предполагаю, что вам понадобится какая-то структура Inverted index. У вас будет Hashmap со словами как клавиши, указывающие на списки пар формы (sentence_id, position). Затем вы сохраняете свои предложения как массивы или связанные списки. Ваш пример будет выглядеть так:

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)} 
}; 

Используя эту структуру, поиск по словам может быть выполнен в постоянное время. Определив нужное слово, поиск предыдущего и последующего слов в данном предложении также может быть выполнен в постоянное время.

Надеюсь, это поможет.