Faire correspondre des lignes contenant un mot avec des permutations

Question

Dites que vous avez une grande table qui contient une colonne varchar.

Comment voulez-vous correspondre les lignes qui contiennent le mot « préféré » dans le varchar col mais les données sont un peu bruyant et contient des erreurs d'orthographe occasionnelles, par exemple:

['$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'] 

Les permutations du mot « préféré » dans les fautes d'orthographe ci-dessus semblent présenter un family resemblance mais il y a très peu de points communs. Notez que découper chaque mot et exécuter levenshtein sur chaque mot de chaque ligne va être prohibitif.

MISE À JOUR:

Il y a quelques autres exemples comme celui-ci, par exemple avec « limité »:

['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

Pourriez-vous l'essayer sur la formation d'un petit échantillon de votre table pour trouver d'éventuelles fautes d'orthographe (en utilisant + scission Levenshtein), puis utiliser la liste de mots résultant sur la table complète?

Answer 2

Vous essayez de faire cela dans TSQL ou dans quelle langue?

Vous pourriez être en mesure d'atteindre la majorité d'entre eux avec une expression régulière.

une certaine variation des éléments suivants

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

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

vous voulez vous assurer que n'est pas sensible casquettes ...

Answer 3

Créer deux autres table, d'orthographes et de speelings possibles:

- - vous pouvez comprendre les types

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'; 

Objection: thi s'll sera lent, et nécessite une configuration. Réponse: pas si lent, et cela devrait être une chose unique pour catégoriser et réparer vos données. Une fois pour l'installation, une fois par ligne entrante à classer.

Answer 4

que je pourrais faire quelque chose comme ça - si vous pouvez vous en sortir avec Levenshtein fois - voici an amazing spellchecker implementation by 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) 

Il fait un ensemble de formation disponible here: http://norvig.com/big.txt Voici un exemple de sortie:

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

Dans votre cas, vous pouvez copier la colonne d'origine dans un nouveau, mais passez-la à travers le correcteur orthographique lorsque vous le faites. Ensuite, placez un index fulltext sur la colonne correctement orthographiée et faites correspondre vos requêtes, mais renvoyez les résultats de la colonne d'origine. Vous n'avez à le faire qu'une fois, par opposition à calculer des distances à chaque fois. Vous pouvez également épeler l'entrée ou vérifier la version corrigée en tant que solution de repli uniquement. De toute façon, cela vaut la peine d'étudier l'exemple de Norvig.