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

Question

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

Йосемитский национальный парк

Йосемитская долина

Йосемитский национальный парк Lodge

Центр посетителей национального парка Йосемити

Сан-Франциско

Парк Золотых Ворот Сан-Франциско

Париж

Нью-Йорк

Манхэттен НовыйЙорк

Гонконг

С другой стороны, у меня есть несколько предложений типа:

1. "Я предложил своей жене 12 ноября 1984 года, во время безумного ливня в центре Йосемити в Калифорнии "
2. " Я люблю гулять со своей собакой в ​​Центральном парке, Нью-Йорк "
3. " Я люблю Гонконг "

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

ребята есть идеи как это сделать?Или, может быть, даже реализация или пакет Python?

Заранее спасибо

Answer 1

Для подобных работ вы обычно используете конвейер обработки чего-либо в следующем порядке:

1. удалить "шумовые" слова (иначе "стоп-слова"), такие как "a", "an", "the", "is" и т. Д. Если вы немного осмотритесь, то сможете найти различные списки стоп-слов для фильтрации.
2. создайте модель векторного пространства каждого «документа» в вашем корпусе.
3. Создание модели векторного пространства запроса.
4. вычисляет что-то вроде TF-IDF или косинусного расстояния между вектором запроса и каждым вектором документа-кандидата.
5. Выберите наивысшую оценку как наиболее вероятное совпадение.

Ссылки

1. Список стоп-слов Onix
2. Список стоп-слов NLTK
3. модель векторного пространства
4. косинус сходства
5. косинус сходства
6. TF-IDF
7. TF-IDF против сходства косинусов

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

Answer 2

Возможно, вы захотите взглянуть на алгоритм Aho-Corasick из Википедии:

В информатике алгоритм Ахо-Корасика - это поиск строк алгоритм, изобретенный Альфредом В. Ахо и Маргарет Дж. Корасик. Это вид алгоритма сопоставления словаря, который находит элементы конечный набор строк («словарь») во входном тексте. Это соответствует всем строкам одновременно. Сложность алгоритма линейный по длине строк плюс длина искомого текст плюс количество совпадений на выходе.

В вашем примере словарь строк - это список мест, а вводимый текст - это предложения. Существует несколько реализаций на нескольких языках, я рекомендую flashtext (Python), следуйте примеру:

from flashtext import KeywordProcessor

keywords = ['Yosemite',
            'Yosemite National Park',
            'Yosemite Valley',
            'Yosemite National Park Lodge',
            'Yosemite National Park Visitor Center',
            'San Francisco',
            'Golden Gate Park San Francisco',
            'Paris',
            'New York',
            'Manhattan New York',
            'Hong Kong']

keyword_processor = KeywordProcessor(case_sensitive=False)
for keyword in keywords:
    keyword_processor.add_keyword(keyword)

sentences = ["I proposed to my wife on the 12th of November 1984, during a crazy downpour in the middle of Yosemite in California",
"I love to walk my dog in Central Park, New York",
"I love Hong Kong"]

for sentence in sentences:
    extracted = keyword_processor.extract_keywords(sentence)
    print(extracted)

выход

['Yosemite']
['New York']
['Hong Kong']