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

Question

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

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

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

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

альтернативный текст http://img7.imageshack.us/img7/4029/indexarb.png

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

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

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

Answer 1

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

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

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

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

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

Ваш алгоритм связывания создаст предложения вроде:

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

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

Answer 2

Полагаю, вам нужна какая-то структура 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)}
};

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

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

Answer 3

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

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 4

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

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

Answer 5

Это достаточно близко, в 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 6

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

Answer 7

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