В средстве проверки правописания, как получить слово, которое находится на расстоянии 3 правок (norvig)

Question

Я пытался использовать корректор орфографии для своей таблицы базы данных, чтобы исправить адрес из одной таблицы, для чего я использовал ссылку http://norvig.com/spell-correct.html Использование таблицы Address_mast в качестве набора строк Я пытаюсь исправить и обновить исправленную строку в "customer_master"

Address_mast

ID        Address
1    sonal plaza,harley road,sw-309012
2    rose apartment,kell road, juniper, la-293889
3    plot 16, queen's tower, subbden - 399081
4    cognizant plaza, abs road, ziggar - 500234

теперь из ссылочного кода это было сделано только для тех слов, которые "на два редактирования от слова". Но я пытаюсь сделать это для 3 или до 4 и в то же время пытаюсь обновить эти исправленные слова в другую таблицу.here - таблица, которая содержит слова с ошибками и должна быть дополнена исправленными словами

Customer_master

Address_1

josely apartmt,kell road, juneeper, la-293889
zoonal plaza, harli road,sw-309012
plot 16, queen's tower, subbden - 399081
cognejantt pluza, abs road, triggar - 500234

вот что я пробовал

import re
import pyodbc
import numpy as np
from collections import Counter

cnxn = pyodbc.connect('DRIVER={SQLServer};SERVER=localhost;DATABASE=DBM;UID=ADMIN;PWD=s@123;autocommit=True')
cursor = cnxn.cursor()
cursor.execute("select address as data  from Address_mast")
data=[]
for row in cursor.fetchall():

    data.append(row[0]) 

data = np.array(data)

def words(text): return re.findall(r'\w+', text.lower())

WORDS = Counter(words(open('data').read()))
def P(word, N=sum(WORDS.values())): 
    "Probability of `word`."
    return WORDS[word] / N

def correction(word): 
    "Most probable spelling correction for word."
    return max(candidates(word), key=P)

def candidates(word): 
    "Generate possible spelling corrections for word."
    return (known([word]) or known(edits1(word)) or known(edits2(word)) or known(edits3(word)) or known(edits4(word)) or [word])

def known(words): 
    "The subset of `words` that appear in the dictionary of WORDS."
    return set(w for w in words if w in WORDS)

def edits1(word):
    "All edits that are one edit away from `word`."
    letters    = 'abcdefghijklmnopqrstuvwxyz'
    splits     = [(word[:i], word[i:])    for i in range(len(word) + 1)]
    deletes    = [L + R[1:]               for L, R in splits if R]
    transposes = [L + R[1] + R[0] + R[2:] for L, R in splits if len(R)>1]
    replaces   = [L + c + R[1:]           for L, R in splits if R for c in letters]
    inserts    = [L + c + R               for L, R in splits for c in letters]
    return set(deletes + transposes + replaces + inserts)

def edits2(word): 
    "All edits that are two edits away from `word`."
    return (e2 for e1 in edits1(word) for e2 in edits1(e1))

def edits3(word): 

    return (e3 for e2 in edits2(word) for e3 in edits1(e2))

def edits4(word): 

    return (e4 for e3 in edits3(word) for e4 in edits1(e3))


sqlstr = ""
j=0
k=0
for i in data:
    sqlstr=" update customer_master set Address='"+correction(data)+"' where data="+correction(data)
    cursor.execute(sqlstr)

    j=j+1
    k=k+cursor.rowcount
cnxn.commit()
cursor.close()
cnxn.close()
print(str(k) +" Records Completed")

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

Answer 1

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

Предположим, у нас есть словарь, хранящийся в объекте set, dict или, в идеале, в объекте collections.Counter, тогда мы можем настроить структуру данных следующим образом:

class VocabTreeNode:
    def __init__(self):
        self.children = {}
        self.word = None
        
    def build(self, vocab):
        for w in vocab:
            self.insert(w)

    def insert( self, word):
        node = self
        for letter in word:
            if letter not in node.children: 
                node.children[letter] = VocabTreeNode()
            node = node.children[letter]
        node.word = word

Для поиска только набора элементов редактируемого расстояния k от слова мы можем снабдить эту структуру рекурсивным поиском.

    def search(self, word, maxCost):
        currentRow = range( len(word) + 1 )    
        results = []
        for letter in self.children:
            self.searchRecursive(self.children[letter], letter, 
                                 word, currentRow, results, 
                                 maxCost)   
        return results
            
    def searchRecursive(self, node, letter, word, previousRow, 
                        results, maxCost):
        columns = len( word ) + 1
        currentRow = [ previousRow[0] + 1 ]
        for column in range( 1, columns ):
            insertCost = currentRow[column - 1] + 1
            deleteCost = previousRow[column] + 1
            if word[column - 1] != letter:
                replaceCost = previousRow[ column - 1 ] + 1
            else:                
                replaceCost = previousRow[ column - 1 ]
            currentRow.append( min( insertCost, deleteCost, replaceCost ) )
    
        if currentRow[-1] <= maxCost and node.word != None:
            results.append( (node.word, currentRow[-1] ) )
        if min( currentRow ) <= maxCost:
            for next_letter in node.children:
                self.searchRecursive( node.children[next_letter], next_letter, word,
                                      currentRow, results, maxCost)

Есть только одна проблема, которую я не знаю, как решить; транспозиции недопустимы как пути, поэтому я не уверен, как включить транспозиции в качестве расстояния редактирования 1 без несколько сложного взлома.

Мой корпус слов был 97722 (набор слов практически в любом дистрибутиве Linux).

sleep(1)
start = time()

for i in range(100):
    x = V.search('elephant',3)
    
print(time()- start)

>>> 17.5 

Это равносильно редактированию вычисления расстояния 3 для этого слова каждые 0,175 секунды. Расстояние редактирования 4 можно было выполнить за 0,377 секунды, в то время как последовательные расстояния редактирования с использованием edits1 быстро приведут к нехватке памяти в вашей системе.

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

Answer 2

Мы можем использовать существующий 1 список редактирования и сделать 1 редактирование для члена в этом списке

Алгоритм: One_Edit_Words = edits1(слово) для каждого в One_Edit_Words сделать edits1 (каждый)

def edit2(word): new = edits1(word) # Get list of all the one edits for i in edits1(word): # Iterate through all the objects in one edit list new.update(edits1(i)) # make one edit for each object and add in list return new # Return list with all the edits

Точно так же мы можем использовать тот же метод, чтобы получить любое количество правок. Ниже функция поможет вам получить 3 правок.

def edit3(word): new = edit2(word)
for i in edit2my(word): new.update(edits1(i)) return new Предупреждение: отнимает слишком много времени даже для небольших вычислений (высокая сложность времени)