Сопоставить строки, содержащие слово с перестановками

Question

Скажем, у вас есть большая таблица, содержащая столбец varchar.

Как бы вы соответствовали строкам, содержащим слово 'предпочитаемый' в столбце varchar, НО данные немного зашумлены и содержат случайные орфографические ошибки, например ::100100

['$2.10 Cumulative Convertible Preffered Stock, $25 par value',
'5.95% Preferres Stock',
'Class A Preffered',
'Series A Peferred Shares',
'Series A Perferred Shares',
'Series A Prefered Stock',
'Series A Preffered Stock',
'Perfered',
'Preffered  C']

Перестановки слова «предпочтительный» в описанных выше ошибках правописания, похоже, показывают семейное сходство , но у них очень мало общего. Обратите внимание, что разделение каждого слова и запуск levenshtein для каждого слова в каждой строке будет непомерно дорогим.

UPDATE:

Есть еще несколько таких примеров, например: с «ограниченным»:

['Resticted Stock Plan',
'resticted securities',
'Ristricted Common Stock',
'Common stock (restrticted, subject to vesting)',
'Common Stock (Retricted)',
'Restircted Stock Award',
'Restriced Common Stock',]

Answer 1

Я мог бы сделать что-то вроде этого - если вам удастся сойтись с Левенштейном один раз - вот удивительная реализация проверки орфографии от Peter Norvig :

import re, collections

def words(text): return re.findall('[a-z]+', text.lower()) 

def train(features):
    model = collections.defaultdict(lambda: 1)
    for f in features:
        model[f] += 1
    return model

NWORDS = train(words(file('big.txt').read()))

alphabet = 'abcdefghijklmnopqrstuvwxyz'

def edits1(word):
   s = [(word[:i], word[i:]) for i in range(len(word) + 1)]
   deletes    = [a + b[1:] for a, b in s if b]
   transposes = [a + b[1] + b[0] + b[2:] for a, b in s if len(b)>1]
   replaces   = [a + c + b[1:] for a, b in s for c in alphabet if b]
   inserts    = [a + c + b     for a, b in s for c in alphabet]
   return set(deletes + transposes + replaces + inserts)

def known_edits2(word):
    return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)

def known(words): return set(w for w in words if w in NWORDS)

def correct(word):
    candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word]
    return max(candidates, key=NWORDS.get)

Он делает доступным обучающий набор здесь: http://norvig.com/big.txt Вот пример вывода:

>>> correct('prefferred')
'preferred'
>>> correct('ristricted')
'restricted'
>>> correct('ristrickted')
'restricted'

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

Answer 2

Пытаетесь сделать это на TSQL или на каком языке?

Возможно, вы сможете поразить большинство из них регулярным выражением.

некоторые изменения из следующих

"p(er|re|e)f{1,2}er{1,2}ed"

"r(e|i)s?t(ri|ir|rti|i)ct?ed"

вы хотите убедиться, что он не чувствителен к заглавным буквам ...

Answer 3

Создайте еще две таблицы написания и возможных написаний:

- вы можете выяснить типы

create table spelling ( id, word ) ; 
create table possible_spelling 
( id, spelling_id references spelling(id), spelling ) 
-- possible spelling also includes the correct spelling
-- all values are lowercase

insert into spelling( word ) values ('preferred');
insert into possible_spelling( spelling_id, spelling ) 
 select 1, '%preferred%' union select 1, '%prefered%' union ....;

select * 
from bigtable a 
join possible_spelling b
on (lower(a.data) like b.spelling )
join spelling c on (b.spelling_id = c.id) 
where c.word = 'preferred';

Возражение: это будет медленно и требует настройки. Ответ: не так медленно, и это должно быть единовременным делом для классификации и исправления ваших данных. Один раз для настройки, один раз для каждой входящей строки для классификации.

Answer 4

Не могли бы вы попробовать натренировать его на небольшом образце таблицы, чтобы найти возможные орфографические ошибки (используя split + Levenshtein), а затем использовать полученный список слов в полной таблице?