Самый эффективный способ индексировать слова в документе?

Question

Это возникло в другом вопросе, но я решил, что лучше задать это как отдельный вопрос. Дайте большой список предложений (порядка 100 тысяч):

[
"This is sentence 1 as an example",
"This is sentence 1 as another example",
"This is sentence 2",
"This is sentence 3 as another example ",
"This is sentence 4"
]

как лучше всего закодировать следующую функцию?

def GetSentences(word1, word2, position):
    return ""

если задано два слова word1, word2 и позиция position, функция должна возвращать список всех предложений, удовлетворяющих этому ограничению. Например:

GetSentences("sentence", "another", 3)

должен возвращать предложения 1 и 3 в качестве индекса предложений. Мой текущий подход использовал словарь, подобный этому:

Index = defaultdict(lambda: defaultdict(lambda: defaultdict(lambda: [])))

for sentenceIndex, sentence in enumerate(sentences):
    words = sentence.split()
    for index, word in enumerate(words):
        for i, word2 in enumerate(words[index:):
            Index[word][word2][i+1].append(sentenceIndex)

Но это быстро приводит к непропорциональным изменениям в наборе данных размером около 130 МБ, поскольку моя 48 ГБ ОЗУ исчерпана менее чем за 5 минут. Мне почему-то кажется, что это обычная проблема, но я не могу найти никаких ссылок на то, как это решить эффективно. Любые предложения о том, как подойти к этому?

Answer 1

Использовать базу данных для хранения значений.

1. Сначала добавить все предложения в одну таблицу (они должны иметь идентификаторы). Вы можете назвать это, например. sentences.
2. Во-вторых, создайте таблицу со словами , содержащимися во всех предложениях (назовите его, например, words, присвойте каждому слову идентификатор), сохранив связь между записями таблицы предложений и записями таблицы слов в отдельных таблица (назовите ее, например, sentences_words, она должна иметь два столбца, предпочтительно word_id и sentence_id).

3. При поиске предложений, содержащих все упомянутые слова, ваша работа будет упрощена:

   1. Сначала вы должны найти записи из words таблицы , где слова - это именно те слова, которые вы ищете. Запрос может выглядеть так:

      SELECT `id` FROM `words` WHERE `word` IN ('word1', 'word2', 'word3');
      

   2. Во-вторых, вы должны найти sentence_id значения из таблицы sentences, для которых требуются word_id значения (соответствующие словам из words таблицы). Исходный запрос может выглядеть так:

      SELECT `sentence_id`, `word_id` FROM `sentences_words`
      WHERE `word_id` IN ([here goes list of words' ids]);
      

      , который можно упростить до этого:

      SELECT `sentence_id`, `word_id` FROM `sentences_words`
      WHERE `word_id` IN (
          SELECT `id` FROM `words` WHERE `word` IN ('word1', 'word2', 'word3')
      );
      

   3. Отфильтруйте результат в Python , чтобы получить только sentence_id значения, которые имеют все необходимые word_id идентификаторы, которые вам нужны.

Это в основном решение, основанное на хранении большого количества данных в форме, которая лучше всего подходит для этого - база данных.

EDIT:

1. Если вы будете искать только два слова, вы можете сделать еще больше (почти все) на стороне СУБД.
2. Учитывая, что вам также нужна разница в позициях, вы должны хранить положение слова в третьем столбце таблицы sentences_words (назовем это просто position), и при поиске подходящих слов вы должны рассчитать разницу этого значения с обоими словами.

Answer 2

Вот как я это сделал на Python.Хотя предполагается, что это нужно делать более одного раза, СУБД является подходящим инструментом для этой работы.Тем не менее, мне кажется, что это хорошо работает с миллионами строк.

sentences = [
    "This is sentence 1 as an example",
    "This is sentence 1 as another example",
    "This is sentence 2",
    "This is sentence 3 as another example ",
    "This is sentence 4"
    ]

sentences = sentences * 200 * 1000

sentencesProcessed = []

def preprocess():
    global sentences
    global sentencesProcessed
    # may want to do a regex split on whitespace
    sentencesProcessed = [sentence.split(" ") for sentence in sentences]

    # can deallocate sentences now
    sentences = None


def GetSentences(word1, word2, position):
    results = []
    for sentenceIndex, sentence in enumerate(sentencesProcessed):
        for wordIndex, word in enumerate(sentence[:-position]):
            if word == word1 and sentence[wordIndex + position] == word2:
                results.append(sentenceIndex)
    return results

def main():
    preprocess()
    results = GetSentences("sentence", "another", 3)
    print "Got", len(results), "results"

if __name__ == "__main__":
    main()