59
Nội dung chính ShowShow
- Làm thế nào để Python thực hiện khoảng cách chỉnh sửa?
- Làm thế nào để bạn tính toán khoảng cách chỉnh sửa?
- Thuật toán khoảng cách chỉnh sửa hoạt động như thế nào?
- Làm thế nào để Python tính khoảng cách Hamming?
Mới! Lưu câu hỏi hoặc câu trả lời và sắp xếp nội dung yêu thích của bạn. Tìm hiểu thêm.Learn more.
Learn more.
Tôi đang lập trình một chương trình kiểm tra chính tả trong Python. Tôi có một danh sách các từ hợp lệ [từ điển] và tôi cần xuất ra một danh sách các từ từ từ điển này có khoảng cách chỉnh sửa là 2 từ một từ không hợp lệ.
Tôi biết tôi cần bắt đầu bằng cách tạo một danh sách với khoảng cách chỉnh sửa của một từ từ không hợp lệ [và sau đó chạy lại trên tất cả các từ được tạo]. Tôi có ba phương thức, chèn [...], xóa [...] và thay đổi [...] sẽ xuất ra danh sách các từ có khoảng cách chỉnh sửa là 1, trong đó chèn xuất ra tất cả các từ hợp lệ với một chữ cái nhiều hơn Từ đã cho, xóa xuất ra tất cả các từ hợp lệ với một chữ cái ít hơn và thay đổi đầu ra tất cả các từ hợp lệ bằng một chữ cái khác.
Tôi đã kiểm tra một loạt các địa điểm nhưng tôi dường như không thể tìm thấy một thuật toán mô tả quá trình này. Tất cả các ý tưởng tôi đã đưa ra liên quan đến việc lặp lại danh sách từ điển nhiều lần, điều này sẽ cực kỳ tốn thời gian. Nếu bất cứ ai có thể cung cấp một số cái nhìn sâu sắc, tôi sẽ vô cùng biết ơn.
Salvador Dali
205K142 Huy hiệu vàng687 Huy hiệu bạc746 Huy hiệu Đồng142 gold badges687 silver badges746 bronze badges142 gold badges687 silver badges746 bronze badges
hỏi ngày 17 tháng 3 năm 2010 lúc 6:02Mar 17, 2010 at 6:02Mar 17, 2010 at 6:02
3
Điều bạn đang xem xét được gọi là một khoảng cách chỉnh sửa và đây là một lời giải thích tốt đẹp trên wiki. Có rất nhiều cách để xác định khoảng cách giữa hai từ và từ mà bạn muốn được gọi là khoảng cách Levenshtein và đây là triển khai DP [Lập trình động] trong Python.
def levenshteinDistance[s1, s2]:
if len[s1] > len[s2]:
s1, s2 = s2, s1
distances = range[len[s1] + 1]
for i2, c2 in enumerate[s2]:
distances_ = [i2+1]
for i1, c1 in enumerate[s1]:
if c1 == c2:
distances_.append[distances[i1]]
else:
distances_.append[1 + min[[distances[i1], distances[i1 + 1], distances_[-1]]]]
distances = distances_
return distances[-1]
Và một vài triển khai khác là ở đây.
0x90
37.9K36 Huy hiệu vàng155 Huy hiệu bạc239 Huy hiệu Đồng36 gold badges155 silver badges239 bronze badges36 gold badges155 silver badges239 bronze badges
Đã trả lời ngày 14 tháng 9 năm 2015 lúc 6:52Sep 14, 2015 at 6:52Sep 14, 2015 at 6:52
Salvador Dalisalvador DaliSalvador DaliSalvador Dali
205K142 Huy hiệu vàng687 Huy hiệu bạc746 Huy hiệu Đồng142 gold badges687 silver badges746 bronze badges142 gold badges687 silver badges746 bronze badges
4
hỏi ngày 17 tháng 3 năm 2010 lúc 6:02Mar 17, 2010 at 6:02
Điều bạn đang xem xét được gọi là một khoảng cách chỉnh sửa và đây là một lời giải thích tốt đẹp trên wiki. Có rất nhiều cách để xác định khoảng cách giữa hai từ và từ mà bạn muốn được gọi là khoảng cách Levenshtein và đây là triển khai DP [Lập trình động] trong Python.
>>> from difflib import get_close_matches
>>> get_close_matches['appel', ['ape', 'apple', 'peach', 'puppy']]
['apple', 'ape']
def levenshteinDistance[s1, s2]:
if len[s1] > len[s2]:
s1, s2 = s2, s1
distances = range[len[s1] + 1]
for i2, c2 in enumerate[s2]:
distances_ = [i2+1]
for i1, c1 in enumerate[s1]:
if c1 == c2:
distances_.append[distances[i1]]
else:
distances_.append[1 + min[[distances[i1], distances[i1 + 1], distances_[-1]]]]
distances = distances_
return distances[-1]
Và một vài triển khai khác là ở đây.ryanjdillon
37.9K36 Huy hiệu vàng155 Huy hiệu bạc239 Huy hiệu Đồng36 gold badges155 silver badges239 bronze badges9 gold badges82 silver badges104 bronze badges
3
Đã trả lời ngày 14 tháng 9 năm 2015 lúc 6:52Sep 14, 2015 at 6:52
Salvador Dalisalvador DaliSalvador DaliJun 11, 2014 at 20:56hỏi ngày 17 tháng 3 năm 2010 lúc 6:02Santosh
Và một vài triển khai khác là ở đây.Apr 29, 2019 at 15:025 silver badges9 bronze badges
1
#this calculates edit distance not levenstein edit distance
word1="rice"
word2="ice"
len_1=len[word1]
len_2=len[word2]
x =[[0]*[len_2+1] for _ in range[len_1+1]]#the matrix whose last element ->edit distance
for i in range[0,len_1+1]: #initialization of base case values
x[i][0]=i
for j in range[0,len_2+1]:
x[0][j]=j
for i in range [1,len_1+1]:
for j in range[1,len_2+1]:
if word1[i-1]==word2[j-1]:
x[i][j] = x[i-1][j-1]
else :
x[i][j]= min[x[i][j-1],x[i-1][j],x[i-1][j-1]]+1
print x[i][j]
37.9K36 Huy hiệu vàng155 Huy hiệu bạc239 Huy hiệu Đồngryanjdillon
Đã trả lời ngày 14 tháng 9 năm 2015 lúc 6:529 gold badges82 silver badges104 bronze badges69 gold badges176 silver badges261 bronze badges
Salvador Dalisalvador DaliNov 12, 2013 at 12:16
def edit_distance[s1, s2]:
m=len[s1]+1
n=len[s2]+1
tbl = {}
for i in range[m]: tbl[i,0]=i
for j in range[n]: tbl[0,j]=j
for i in range[1, m]:
for j in range[1, n]:
cost = 0 if s1[i-1] == s2[j-1] else 1
tbl[i,j] = min[tbl[i, j-1]+1, tbl[i-1, j]+1, tbl[i-1, j-1]+cost]
return tbl[i,j]
print[edit_distance["Helloworld", "HalloWorld"]]
>>> from difflib import get_close_matches
>>> get_close_matches['appel', ['ape', 'apple', 'peach', 'puppy']]
['apple', 'ape']
>>> from difflib import get_close_matches
>>> get_close_matches['appel', ['ape', 'apple', 'peach', 'puppy']]
['apple', 'ape']
from difflib import SequenceMatcher
a = 'kitten'
b = 'sitting'
required_edits = [
code
for code in [
SequenceMatcher[a=a, b=b, autojunk=False]
.get_opcodes[]
]
if code[0] != 'equal'
]
required_edits
# [
# # [tag, i1, i2, j1, j2]
# ['replace', 0, 1, 0, 1], # replace a[0:1]="k" with b[0:1]="s"
# ['replace', 4, 5, 4, 5], # replace a[4:5]="e" with b[4:5]="i"
# ['insert', 6, 6, 6, 7], # insert b[6:7]="g" after a[6:6]="n"
# ]
# the edit distance:
len[required_edits] # == 3
Từ các tài liệuSantoshJun 1, 2020 at 16:03
Đã trả lời ngày 29 tháng 4 năm 2019 lúc 15:025 silver badges9 bronze badgeskrassowski
Ryanjdillonryanjdillon4 gold badges51 silver badges84 bronze badges
1
16.5k9 Huy hiệu vàng82 Huy hiệu bạc104 Huy hiệu đồng69 gold badges176 silver badges261 bronze badges
Đây là phiên bản của tôi cho khoảng cách LevenshteinNov 12, 2013 at 12:16
In [2]: Levenshtein.distance["foo", "foobar"]
Out[2]: 3
In [3]: Levenshtein.distance["barfoo", "foobar"]
Out[3]: 6
In [4]: Levenshtein.distance["Buroucrazy", "Bureaucracy"]
Out[4]: 3
In [5]: Levenshtein.distance["Misisipi", "Mississippi"]
Out[5]: 3
In [6]: Levenshtein.distance["Misisipi", "Misty Mountains"]
Out[6]: 11
In [7]: Levenshtein.distance["Buroucrazy", "Born Crazy"]
Out[7]: 4
Đã trả lời ngày 11 tháng 6 năm 2014 lúc 20:56
SantoshsantoshJun 1, 2020 at 16:03Oct 12, 2021 at 19:023285 Huy hiệu bạc9 Huy hiệu Đồngkrassowskifirelynx
Frazman4 gold badges51 silver badges84 bronze badges8 gold badges85 silver badges95 bronze badges
30.9K69 Huy hiệu vàng176 Huy hiệu bạc261 Huy hiệu Đồng
- Đã trả lời ngày 12 tháng 11 năm 2013 lúc 12:16
- Sử dụng
2 từ Python tích hợp>>> from difflib import get_close_matches >>> get_close_matches['appel', ['ape', 'apple', 'peach', 'puppy']] ['apple', 'ape']
0 là một cách khác để thực hiện nó, nhưng [như được chỉ ra chính xác trong các bình luận], kết quả không khớp với định nghĩa của khoảng cách chỉnh sửa chính xác. Phần thưởng: Nó hỗ trợ bỏ qua các bộ phận "rác" [ví dụ: không gian hoặc dấu câu].Oct 12, 2021 at 19:02>>> from difflib import get_close_matches >>> get_close_matches['appel', ['ape', 'apple', 'peach', 'puppy']] ['apple', 'ape']
>>> from difflib import get_close_matches
>>> get_close_matches['appel', ['ape', 'apple', 'peach', 'puppy']]
['apple', 'ape']
Đã trả lời ngày 1 tháng 6 năm 2020 lúc 16:03firelynxNov 12, 2020 at 14:16
2
Krassowskikrassowski8 gold badges85 silver badges95 bronze badges
Huy hiệu vàng 11.6K451 Huy hiệu bạc84 Huy hiệu đồng
Tôi sẽ khuyên bạn không tự tạo loại mã này. Có các thư viện cho điều đó.
Ví dụ, Thư viện Levenshtein.9 gold badges46 silver badges53 bronze badges
Đã trả lời ngày 12 tháng 10 năm 2021 lúc 19:02Apr 1, 2017 at 12:54
jt26jt26jt26jt26
Đã trả lời ngày 12 tháng 11 năm 2020 lúc 14:163 bronze badges3 bronze badges
Thay vì đi với khoảng cách Levenshtein Algo sử dụng cây BK hoặc trie, vì các thuật toán này có độ phức tạp ít hơn sau đó chỉnh sửa khoảng cách. Duyệt tốt về những chủ đề này sẽ đưa ra một mô tả chi tiết.
Liên kết này sẽ giúp bạn nhiều hơn về kiểm tra chính tả.
>>> from difflib import get_close_matches
>>> get_close_matches['appel', ['ape', 'apple', 'peach', 'puppy']]
['apple', 'ape']
PacholikDec 3, 2018 at 18:44Dec 3, 2018 at 18:44
8.3369 Huy hiệu vàng46 Huy hiệu bạc53 Huy hiệu Đồng
>>> from difflib import get_close_matches
>>> get_close_matches['appel', ['ape', 'apple', 'peach', 'puppy']]
['apple', 'ape']
Đã trả lời ngày 1 tháng 4 năm 2017 lúc 12:54Apr 25 at 4:39Apr 25 at 4:39
Phù hiệu bằng đồng 213
>>> from difflib import get_close_matches
>>> get_close_matches['appel', ['ape', 'apple', 'peach', 'puppy']]
['apple', 'ape']
Bạn cần khoảng cách chỉnh sửa tối thiểu cho nhiệm vụ này.Jun 8 at 16:33Jun 8 at 16:33
Sau đây là phiên bản Med A.K.A Levenshtein của tôi.Harry MorenoHarry Moreno
Đã trả lời ngày 3 tháng 12 năm 2018 lúc 18:447 gold badges59 silver badges105 bronze badges7 gold badges59 silver badges105 bronze badges
Làm thế nào để Python thực hiện khoảng cách chỉnh sửa?
Dưới đây là chức năng đệ quy. def edit_distance_recurse [seq1, seq2, operations = []]: "" "Trả về khoảng cách chỉnh sửa giữa hai chuỗi được cung cấp." "" Nếu seq1 [0] == seq2 [0] Thay đổi cho ký tự `{SEQ1 [0]}`. "]def edit_distance_recurse[seq1, seq2, operations=[]]: """Returns the Edit Distance between the provided two sequences.""" if seq1[0] == seq2[0]: operations = operations + [f"Make no change for character `{seq1[0]}`."]def edit_distance_recurse[seq1, seq2, operations=[]]: """Returns the Edit Distance between the provided two sequences.""" if seq1[0] == seq2[0]: operations = operations + [f"Make no change for character `{seq1[0]}`."]
Làm thế nào để bạn tính toán khoảng cách chỉnh sửa?
Xóa 'ký tự m'th của str1 và tính toán khoảng cách chỉnh sửa giữa các ký tự' m-1 'của các ký tự str1 và' n 'của str2.Đối với tính toán này, chúng ta chỉ cần thực hiện-[1 + mảng [m-1] [n]] trong đó 1 là chi phí xóa hoạt động và mảng [m-1] [n] là chỉnh sửa khoảng cách giữa 'm-1'ký tự của các ký tự str1 và 'n' của str2.- [1 + array[m-1][n]] where 1 is the cost of delete operation and array[m-1][n] is edit distance between 'm-1' characters of str1 and 'n' characters of str2.- [1 + array[m-1][n]] where 1 is the cost of delete operation and array[m-1][n] is edit distance between 'm-1' characters of str1 and 'n' characters of str2.
Thuật toán khoảng cách chỉnh sửa hoạt động như thế nào?
Trong ngôn ngữ học tính toán và khoa học máy tính, khoảng cách chỉnh sửa là một số liệu chuỗi, tức là cách định lượng cách hai chuỗi khác nhau [ví dụ: các từ] với nhau, được đo bằng cách đếm số lượng hoạt động tối thiểu cần thiết để biến đổi một chuỗi vàokhác.measured by counting the minimum number of operations required to transform one string into the other.measured by counting the minimum number of operations required to transform one string into the other.
Làm thế nào để Python tính khoảng cách Hamming?
Khoảng cách cản giữa hai vectơ chỉ đơn giản là tổng của các phần tử tương ứng khác nhau giữa các vectơ.Khoảng cách Hamming giữa hai vectơ sẽ là 2, vì đây là tổng số phần tử tương ứng có các giá trị khác nhau.the sum of corresponding elements that differ between the vectors. The Hamming distance between the two vectors would be 2, since this is the total number of corresponding elements that have different values.the sum of corresponding elements that differ between the vectors. The Hamming distance between the two vectors would be 2, since this is the total number of corresponding elements that have different values.