# 定义初始矩阵，初始为0
In [1]: len_str1 = 3

In [2]: len_str2 = 4

In [3]: [0 for n in range(len_str1 * len_str2)]
Out[3]: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

In [4]: len([0 for n in range(len_str1 * len_str2)])
Out[4]: 12

def edit(str1, str2):
    len_str1 = len(str1) + 1
    len_str2 = len(str2) + 1
    # 定义一个矩阵
    matrix = [0 for n in range(len_str1 * len_str2)]
    # 初始化
    for x in range(len_str1):
        matrix[x] = x
    for y in range(0, len(matrix), len_str1):
        if y % len_str1 == 0:
                matrix[y] = y // len_str1
    '''
    1.  1. 最上和最左相等为左上方数字，不等则为左上方加一
        2.  左方加一
        3.  上方加一

    上面三个取最小值
    '''
    for x in range(1, len_str1):
        for y in range(1, len_str2):
            if str1[x - 1] == str2[y - 1]:
                cost = 0
            else:
                cost = 1
            matrix[y * len_str1 + x] = min(matrix[(y - 1) * len_str1 + x] + 1,
                                           matrix[y * len_str1 + (x - 1)] + 1,
                                           matrix[(y - 1) * len_str1 + (x - 1)] + cost)

    '''2. 取右下角值 为 最小编辑距离'''
    return matrix[-1]


if __name__ == '__main__':
    i = edit('speak', 'safe')
    print i

# 字母拼写的所有可能的结果
In [11]: word = "ab"

In [12]: letters = 'abcdefghijklmnopqrstuvwxyz'

In [13]: 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]
    ...:

In [17]: set(deletes + transposes + replaces + inserts)
    ...:
Out[17]:
{'a',
 'aa',
 'aab',
 'ab',
 'aba',
 'abb',
 'abc',
 'abd',
 'abe',
 'abf',
 'abg',
 'abh',
 'abi',
 'abj',
 'abk',
 'abl',
 'abm',
 'abn',
 'abo',
 'abp',
 'abq',
 'abr',
 'abs',
 'abt',
 'abu',
 'abv',
 'abw',
 'abx',
 'aby',
 'abz',
 'ac',
 'acb',
 'ad',
 'adb',
 'ae',
 'aeb',
 'af',
 'afb',
 'ag',
 'agb',
 'ah',
 'ahb',
 'ai',
 'aib',
 'aj',
 'ajb',
 'ak',
 'akb',
 'al',
 'alb',
 'am',
 'amb',
 'an',
 'anb',
 'ao',
 'aob',
 'ap',
 'apb',
 'aq',
 'aqb',
 'ar',
 'arb',
 'as',
 'asb',
 'at',
 'atb',
 'au',
 'aub',
 'av',
 'avb',
 'aw',
 'awb',
 'ax',
 'axb',
 'ay',
 'ayb',
 'az',
 'azb',
 'b',
 'ba',
 'bab',
 'bb',
 'cab',
 'cb',
 'dab',
 'db',
 'eab',
 'eb',
 'fab',
 'fb',
 'gab',
 'gb',
 'hab',
 'hb',
 'iab',
 'ib',
 'jab',
 'jb',
 'kab',
 'kb',
 'lab',
 'lb',
 'mab',
 'mb',
 'nab',
 'nb',
 'oab',
 'ob',
 'pab',
 'pb',
 'qab',
 'qb',
 'rab',
 'rb',
 'sab',
 'sb',
 'tab',
 'tb',
 'uab',
 'ub',
 'vab',
 'vb',
 'wab',
 'wb',
 'xab',
 'xb',
 'yab',
 'yb',
 'zab',
 'zb'}

In [18]:

def edits1(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):
    return (e2 for e1 in edits1(word) for e2 in edits1(e1))

# -*- coding:utf-8 -*-


def edits1(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):
    return (e2 for e1 in edits1(word) for e2 in edits1(e1))



if __name__ == '__main__':
    # edits1('study')
    i = edits2('study')
    print i


'''
结果是一个生成器
<generator object <genexpr> at 0x00000000029AD120>
'''

# -*- coding:utf-8 -*-

import re
from collections import Counter


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

# 统计出现的单词
WORDS = Counter(words(open('big.txt').read()))


# word_list = {}
# with open('big.txt') as f:
#     for line in f:
#         line = line.replace(",", " ")
#         line = line.replace(".", " ")
#         line = line.replace("!", " ")
#         words = line.split()
#         for word in words:
#             if word_list.has_key(word):
#                 word_list[word] += 1
#             else:
#                 word_list[word] = 1
#     result = sorted(word_list.items(), key=lambda k: k[1], reverse=True)


def edits1(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):
    return (e2 for e1 in edits1(word) for e2 in edits1(e1))

# 在已知的单词中进行匹配
def known(words):
    return set(w for w in words if w in WORDS)


if __name__ == '__main__':
    # edits1('study')
    # i = edits2('study')
    # print i
    a = known(edits2('studa'))
    print a


'''
结果
set(['tula', 'stump', 'sta', 'sturdy', 'sudan', 'stung', 'studio', 'stuck', 'stuff', 'stead', 'squad', 'stud', 'soda', 'souza', 'study', 'shuya'])

'''