Алгоритм поиска предложений в тексте - PullRequest
Новая
       31

Алгоритм поиска предложений в тексте

0 голосов
/ 29 марта 2020

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

Может быть, здесь будет хороший пример. Предположим, нам нужно найти фразу «все белые кошки» из этого текста:

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

Если предположить, что «это» слово имеет число 30, то мы можем создать эти числа для каждого слова Исходная фраза: 

all: 48, 57, 76
white: 51, 60, 67
cats: 37, 49, 58, 68, 80

Как видите, мы можем объединить эти слова в разные фазы, и каждая «фраза» будет иметь свое «качество». Качество можно рассчитать как сумму расстояний от каждого слова до виртуального «центра фраз».

" all cats white " - это две хорошие фразы с качество 3,33. Все остальные слова можно комбинировать с фразами, но они будут низкого качества.

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

Чтобы упростить, я думаю, чтобы ограничить поиск расстояние (скажем, 5 слов) от каждого слова.

Но затем я не могу себе представить, как рассчитать это быстрее.

Я чувствую, что для этого есть готовый алгоритм, но могу t найти один.

Спасибо!

1 Ответ

1 голос
/ 29 марта 2020

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

См. Реализацию модели в Python: 

def calculate_score(data):
    def score(positions):
        center = sum(positions) / len(positions)
        return sum(abs(p - center) for p in positions)

    word_set = set(data)
    word_count = len(word_set)
    pos_words = {p: word for word, positions in data.items() for p in positions}
    positions = sorted(pos_words)
    return [
        (positions[i], score(positions[i:i+word_count]))
        for i in range(len(positions) - word_count + 1)
        if set(pos_words[positions[i+j]] for j in range(word_count)) == word_set
    ]

data = {
    "all": [48, 57, 76],
    "white": [51, 60, 67],
    "cats": [37, 49, 58, 68, 80],
}

print(calculate_score(data))

Результат содержит позиции первого слова триплета вместе с вычисленными баллами. 

[(48, 3.3333333333333357),
 (49, 9.333333333333336),
 (51, 8.666666666666664),
 (57, 3.3333333333333357),
 (67, 11.333333333333329)]
...