Учитывая, что
- у вас есть словарь (то есть список) определенных имен, которые вы ищете
- вы делаете это для английского языка, который может быть tokenised относительно простым способом (например, с использованием пробелов и знаков препинания в качестве границ токенов)
должен хорошо работать следующий подход:
- Подготовить словарьимен в вашем списке
- Маркируйте текст
- Рассмотрите a) каждый токен, b) каждую пару последовательных токенов, c) каждую тройку последовательных токенов как имена кандидатов и ищите их всловарь с использованием методов приблизительного сопоставления строк .
Существует несколько возможных стратегий для реализации приблизительного сопоставления строк (я бы рекомендовал сначала попробовать (E) ниже):
A) Методы, которые сокращают строку и все словарные записи до канонической формы перед поиском. Soundex является одним из таких методов.Основная общая проблема этих методов заключается в том, что они не обеспечивают ранжирование по сходству строк , поэтому вы можете получить много разных кандидатов, но не знаете, какой из них лучше всего подходит.Кроме того, каноническая форма основана на правилах произношения для определенных языков (например, Soundex для английского), что не подходит для имен, особенно неанглийских.Это также проблематично, потому что ошибки, с которыми вы сталкиваетесь, вероятно, вызваны опечаткой, а не неправильным произношением имени.Например, использование «q» вместо «w» может быть частой проблемой для вас, потому что «q» и «w» расположены рядом друг с другом на клавиатуре , в то время как их произношение совершенно разное.
B) Методы, использующие поиск по дереву для реализации словаря.Во время поиска в дереве вы можете учесть одно или два несоответствия и, таким образом, найти кандидатов с ошибками.Основная проблема здесь заключается в том, что поиск обычно становится недопустимо медленным, как только вы допускаете более двух несоответствий символов, особенно когда несоответствия допускаются в начале строк.Однако есть определенные способы оптимизировать производительность.См. здесь для нескольких идей.
C) Методы, основанные на n-грамм поиска.Здесь вы можете использовать хеш-таблицу для реализации словаря, но вместо того, чтобы помещать имена в хеш напрямую, вы разбиваете каждое имя на его символьные n-граммы (для предопределенных n, обычно 2 или 3) и помещаете n-граммы всловарь.Например, для
hemingway
вы положите
hem
emi
min
ing
ngw
gwa
way
в хеш.Во время поиска вы проделываете то же самое со строкой-кандидатом, просматриваете все ее n-граммы и принимаете это имя, которое имеет наибольшее количество n-граммов, общее с вводом.Например, если введено значение hemmgway, вы обнаружите, что оно имеет три н-грамма (hem, gwa, way), общие с записью словаря hemingway.
Этот метод работает относительно хорошо, если ваши строки довольно длинные и содержат только несколько ошибок здесь и там.Возможно, в вашем случае это тоже не оптимально, но вы можете попробовать.
D) Методы, использующие автоматы Левенштейна для реализации словаря.Это относительно сложный метод, а также возникают проблемы, когда вы хотите допустить очень большое количество ошибок.Подробное описание можно найти в этой статье Шульца и Михова.Я не уверен, существует ли готовая к использованию реализация с открытым исходным кодом.
E) Методы, которые объединяют реализацию Левенштейнафункция редактирования расстояния с метрическим деревом .Учитывая ваше описание, я считаю, что это будет работать лучше для вас, и я сам использовал этот метод в аналогичной ситуации.Дальнейшие ссылки вы найдете в ответах на этот вопрос SO и ссылку на реализацию (хотя я еще не пробовал) в этом вопросе SO .