Какова хорошая стратегия для группировки похожих слов?

Question

Скажем, у меня есть список названий фильмов с орфографическими ошибками и небольшими вариациями, такими как это -

 "Pirates of the Caribbean: The Curse of the Black Pearl"
 "Pirates of the carribean"
 "Pirates of the Caribbean: Dead Man's Chest"
 "Pirates of the Caribbean trilogy"
 "Pirates of the Caribbean"
 "Pirates Of The Carribean"

Как мне сгруппировать или найти такие наборы слов, предпочтительно используя python и / или redis?

Answer 1

Посмотрите на "нечеткое соответствие".Некоторые замечательные инструменты в теме ниже, которая вычисляет сходство между строками.

Мне особенно нравится модуль difflib

>>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])
['apple', 'ape']
>>> import keyword
>>> get_close_matches('wheel', keyword.kwlist)
['while']
>>> get_close_matches('apple', keyword.kwlist)
[]
>>> get_close_matches('accept', keyword.kwlist)
['except']

https://stackoverflow.com/questions/682367/good-python-modules-for-fuzzy-string-comparison

Answer 2

Вы можете заметить, что похожие строки имеют большую общую подстроку, например:

"Bla bla bLa" и "Bla bla bRa" => общая подстрока - "Bla bla ba" (обратите внимание натретье слово)

Чтобы найти общую подстроку, вы можете использовать алгоритм динамического программирования.Один из вариантов алгоритма - Расстояние Левенштейна (расстояние между наиболее похожими строками очень мало, а между более разными строками расстояние больше) - http://en.wikipedia.org/wiki/Levenshtein_distance.

Также для быстрого выполнения выможет попытаться адаптировать алгоритм Soundex - http://en.wikipedia.org/wiki/Soundex.

Таким образом, после вычисления расстояния между всеми вашими строками, вы должны их кластеризовать.Самый простой способ - это k-означает (но для этого необходимо определить количество кластеров).Если вы на самом деле не знаете количество кластеров, вы должны использовать иерархическую кластеризацию. Обратите внимание, что количество кластеров в вашей ситуации составляет количество заголовков различных фильмов + 1 (для абсолютно плохо записанных строк).

Answer 3

Чтобы добавить еще один совет к ответу Фредрика, вы также можете получить вдохновение от поисковых систем подобного кода, такого как этот:

def dosearch(terms, searchtype, case, adddir, files = []):
    found = []
    if files != None:
        titlesrch = re.compile('>title<.*>/title<')
        for file in files:
            title = ""
            if not (file.lower().endswith("html") or file.lower().endswith("htm")):
                continue
            filecontents = open(BASE_DIR + adddir + file, 'r').read()
            titletmp = titlesrch.search(filecontents)
            if titletmp != None:
                title = filecontents.strip()[titletmp.start() + 7:titletmp.end() - 8]
            filecontents = remove_tags(filecontents)
            filecontents = filecontents.lstrip()
            filecontents = filecontents.rstrip()
            if dofind(filecontents, case, searchtype, terms) > 0:
                found.append(title)
                found.append(file)
    return found

Источник и более подробная информация: http://www.zackgrossbart.com/hackito/search-engine-python/

С уважением,

Макс

Answer 4

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

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

Answer 5

Я считаю, что на самом деле есть две разные проблемы.

Первое - это исправление заклинаний. Вы можете иметь его в Python здесь

http://norvig.com/spell-correct.html

Второй более функциональный. Вот что я буду делать после исправления заклинания. Я бы сделал функцию отношения.

относящиеся (предложение 1, предложение 2) тогда и только тогда, когда в предложении 1 и предложении 2 встречаются редкие общие слова. Под редкими я подразумеваю слова, отличные от (что, что, и т. Д.). Вы можете взглянуть на систему TF / IDF, чтобы определить, связаны ли два документа, используя их слова. Просто немного погуглив, я нашел это:

https://code.google.com/p/tfidf/