Khoảng cách levenshtein python sklearn

Tôi muốn thực hiện tìm kiếm hàng xóm gần nhất trên khoảng cách Levenshtein với bộ dữ liệu văn bản bằng Python. Tìm kiếm có thể là gần đúng, nên được triển khai bằng cách sử dụng các thư viện Python cốt lõi và các truy vấn phải là hoạt động gần như liên tục. Dưới đây, tôi liệt kê một số triển khai mà tôi đã xem xét cùng với những sai sót của chúng

Cách tiếp cận vũ phu ngây thơ

Một giải pháp brute-force ngây thơ liên quan đến việc tính toán khoảng cách Levenshtein theo cặp giữa một truy vấn và tất cả các văn bản trong tập dữ liệu

$ pip install numpy python-Levenshtein
$ python
>>> import Levenshtein
>>> import numpy as np
>>>
>>> texts = ["Some string", "Some other string", "Yet another string"]
>>> query = "Smeo srting"
>>> knn = 2
>>>
>>> distances = [Levenshtein.distance(query, text) for text in texts]
>>> for idx in np.argsort(distances)[:knn]:
..     print(f'{texts[idx]}, {distances[idx]}')
...
Some string, 4
Some other string, 8

Tuy nhiên, cách tiếp cận ngây thơ là khá chậm. Đối với M văn bản có độ dài văn bản tối đa N, tìm kiếm K hàng xóm gần nhất của truy vấn là thao tác O(M * N^2). Tìm K hàng xóm gần nhất cho mỗi văn bản trong số M văn bản sau đó là thao tác O(M^2 * N^2)

lập chỉ mục số liệu

Một giải pháp mà tôi đã xem xét là lập chỉ mục số liệu. Lập chỉ mục số liệu cho phép tốc độ tìm kiếm K-láng giềng gần nhất trong không gian số liệu tốt hơn so với ngây thơ. Các đơn vị được lập chỉ mục không cần phải là vectơ, chúng chỉ cần được trang bị hàm khoảng cách để chúng tạo thành một không gian số liệu. Các chuỗi được trang bị khoảng cách Levenshtein tạo thành một không gian số liệu

Một đặc điểm thú vị của việc học số liệu là nó được triển khai trong các thư viện cốt lõi của Python, chẳng hạn như việc triển khai chỉ mục cây bóng trong

cities = {"Pittsburgh":"Pennsylvania",
          "Tucson":"Arizona",
          "Cincinnati":"Ohio",
          "Albuquerque":"New Mexico",
          "Culpeper":"Virginia",
          "Asheville":"North Carolina",
          "Worcester":"Massachusetts",
          "Manhattan":"New York",
          "Phoenix":"Arizona",
          "Niagara Falls":"New York"} 

5. Với cây bóng, việc tìm kiếm K hàng xóm gần nhất của a trở thành phép toán O(log M * N^2). Tìm K hàng xóm gần nhất cho mỗi văn bản trong số M văn bản sau đó là thao tác O(M log M * N^2)

Một nhược điểm của việc triển khai sklearn là nó yêu cầu các vectơ float trên đầu vào. Do đó, một lược đồ ánh xạ từ chuỗi sang vectơ float và ngược lại dường như là bắt buộc. Giải pháp có thể đại diện cho bộ dữ liệu lên tới 2^53 chuỗi, điều này dường như là đủ

$ pip install sklearn python-Levenshtein
$ python
>>> from typing import Optional
>>> import Levenshtein
>>> import numpy as np
>>> from sklearn.neighbors import BallTree, DistanceMetric
>>> 
>>> texts = ["Some string", "Some other string", "Yet another string"]
>>> query = "Smeo srting"
>>> knn = 2
>>> 
>>> def text_to_vector(text: str, idx: Optional[int] = None) -> np.ndarray:
..     if idx is None:
..         idx = len(texts)
..         texts.append(text)
..     return np.array([idx], dtype=np.float64)
.. 
>>> def vector_to_text(idx: np.ndarray) -> str:
..     return texts[int(idx[0])]
.. 
>>> def levdist(x: np.ndarray, y: np.ndarray) -> int:
..     x, y = map(vector_to_text, (x, y))
..     return Levenshtein.distance(x, y)
.. 
>>> X = [text_to_vector(text, idx) for idx, text in enumerate(texts)]
>>> x = [text_to_vector(query)]
>>> 
>>> tree = BallTree(X, metric=DistanceMetric.get_metric('pyfunc', func=levdist))
>>> (dists,), (idxs,) = tree.query(x, k=knn)
>>> for dist, idx in zip(dists, idxs):
..    print(f'{texts[idx]}, {int(dist)}')
.. 
Some string, 4
Some other string, 8

Tuy nhiên, tốc độ dường như vẫn là một nhược điểm lớn. Tôi sẽ đánh giá cao các con trỏ tới các thư viện cung cấp tìm kiếm K-láng giềng gần nhất trên khoảng cách Levenshtein hoặc trên các không gian số liệu trong thời gian gần O(M * N^2)

Chương này đề cập đến khoảng cách Levenshtein và trình bày một số triển khai Python cho phép đo này. Có rất nhiều trường hợp sử dụng cho khoảng cách Levenshtein. Khoảng cách Levenshtein và các ý tưởng cơ bản được sử dụng rộng rãi trong các lĩnh vực như khoa học máy tính, ngôn ngữ máy tính và thậm chí cả tin sinh học, sinh học phân tử, phân tích DNA. Bạn thậm chí có thể đo sự giống nhau của giai điệu hoặc nhịp điệu trong âm nhạc1. Khoảng cách Levenshtein đã thấm nhuần cuộc sống hàng ngày của chúng ta. Bất cứ khi nào bạn sử dụng một chương trình hoặc ứng dụng bằng cách sử dụng một số hình thức kiểm tra chính tả và sửa lỗi, rất có thể các lập trình viên đã sử dụng "chỉnh sửa khoảng cách" hay còn được gọi là "khoảng cách Levenshtein"

Bạn có thể đã gặp một trường hợp sử dụng khả thi khác cho khái niệm này. Hãy tưởng tượng rằng bạn đang sử dụng một từ điển Python, trong đó bạn sử dụng các chuỗi làm khóa

Chúng ta hãy xem từ điển ví dụ sau với các tên thành phố của Hoa Kỳ thường bị sai chính tả

cities = {"Pittsburgh":"Pennsylvania",
          "Tucson":"Arizona",
          "Cincinnati":"Ohio",
          "Albuquerque":"New Mexico",
          "Culpeper":"Virginia",
          "Asheville":"North Carolina",
          "Worcester":"Massachusetts",
          "Manhattan":"New York",
          "Phoenix":"Arizona",
          "Niagara Falls":"New York"} 

Vì vậy, việc cố gắng lấy các tên trạng thái tương ứng thông qua các lần truy cập từ điển sau đây sẽ làm phát sinh các ngoại lệ

>>> s = "Mannhattan"
>>> s = s[:2] + s[3:]
>>> s
'Manhattan'

2

Nếu người đọc nhìn vào những lỗi chính tả này, họ sẽ dễ dàng nhận ra thành phố mà bạn đang nghĩ đến. Mặt khác, từ điển Python là mô phạm và không thể tha thứ. Nó chỉ chấp nhận một khóa, nếu nó giống hệt nhau

Câu hỏi đặt ra là hai chuỗi giống nhau ở mức độ nào?

Số liệu chuỗi là số liệu đo khoảng cách giữa hai chuỗi văn bản. Một trong những số liệu chuỗi được biết đến nhiều nhất là cái gọi là Khoảng cách Levenshtein, còn được gọi là Khoảng cách chỉnh sửa. Levenshtein tính toán số lần thay thế và xóa cần thiết để biến một chuỗi này thành một chuỗi khác

Đào tạo Python trực tiếp

Thưởng thức trang này?

Nhìn thấy. Tổng quan về các khóa học Python trực tiếp

đăng ký tại đây

Khoảng cách chỉnh sửa tối thiểu hoặc Khoảng cách Levenshtein

Khoảng cách chỉnh sửa tối thiểu giữa hai chuỗi là số thao tác chỉnh sửa tối thiểu cần thiết để chuyển đổi chuỗi này thành chuỗi khác. Các hoạt động chỉnh sửa có thể bao gồm chèn, xóa và thay thế

Các tập hợp thao tác chỉnh sửa đơn giản nhất có thể được định nghĩa là

• Chèn một biểu tượng duy nhất. Điều này có nghĩa là chúng ta thêm một ký tự vào một chuỗi s. Thí dụ. Nếu chúng ta có chuỗi s = "Manhatan", chúng ta có thể chèn ký tự "t" để viết đúng chính tả

  >>> s = "Manhatan"
  >>> s = s[:5] + "t" + s[5:]
  >>> print(s)
  Manhattan
  

• Xóa một ký hiệu Ví dụ

  >>> s = "Mannhattan"
  >>> s = s[:2] + s[3:]
  >>> s
  'Manhattan'
  

• Thay một ký hiệu đơn Trong ví dụ sau, chúng ta phải thay chữ “o” thành chữ “a” để viết đúng chính tả.

  >>> s = "Manhatton"
  >>> s = s[:7] + "a" + s[8:]
  >>> s
  'Manhattan'
  

Khoảng cách chỉnh sửa tối thiểu giữa hai chuỗi "Mannhaton" và "Manhattan" tương ứng với giá trị 3, vì chúng ta cần ba thao tác chỉnh sửa cơ bản để biến chuỗi thứ nhất thành chuỗi thứ hai

>>> s = "Mannhaton"
>>> s = s[:2] + s[3:]         # deletion
>>> s
'Manhaton'
>>> s = s[:5] + "t" + s[5:]   # insertion
>>> s
'Manhatton'
>>> s = s[:7] + "a" + s[8:]   # substitution
>>> s
'Manhattan'

Chúng tôi có thể gán trọng số hoặc chi phí cho từng thao tác chỉnh sửa này, chẳng hạn như. g. đặt mỗi người trong số họ thành 1. Cũng có thể lập luận rằng thay thế sẽ đắt hơn so với chèn hoặc xóa, vì vậy đôi khi chi phí thay thế được đặt thành 2

Định nghĩa toán học của khoảng cách Levenshtein

Khoảng cách Levenshtein giữa hai chuỗi a và b được cho bởi leva,b(len(a), len(b)) trong đó leva,b(i, j) bằng

• max(i, j) nếu min(i, j)=0
• nếu không thì. ________số 8

trong đó 1ai≠bj là hàm chỉ thị bằng 0 khi ai=bj và bằng 1 nếu ngược lại, và leva,b(i, j) là khoảng cách giữa i ký tự đầu tiên của a và j ký tự đầu tiên của b

Khoảng cách Levenshtein có các thuộc tính sau

• Nó bằng 0 khi và chỉ khi các chuỗi bằng nhau
• Nó ít nhất là sự khác biệt về kích thước của hai chuỗi
• Nó nhiều nhất là chiều dài của chuỗi dài hơn
• Bất đẳng thức tam giác. Khoảng cách Levenshtein giữa hai chuỗi không lớn hơn tổng khoảng cách Levenshtein của chúng từ chuỗi thứ ba

Đào tạo Python trực tiếp

Thưởng thức trang này?

Nhìn thấy. Tổng quan về các khóa học Python trực tiếp

đăng ký tại đây

Hàm Levenshtein đệ quy trong Python

Hàm Python sau triển khai khoảng cách Levenshtein theo cách đệ quy

def LD(s, t):
    if s == "":
        return len(t)
    if t == "":
        return len(s)
    if s[-1] == t[-1]:
        cost = 0
    else:
        cost = 1
       
    res = min([LD(s[:-1], t)+1,
               LD(s, t[:-1])+1, 
               LD(s[:-1], t[:-1]) + cost])

    return res

print(LD("Python", "Peithen"))

ĐẦU RA

$ pip install sklearn python-Levenshtein
$ python
>>> from typing import Optional
>>> import Levenshtein
>>> import numpy as np
>>> from sklearn.neighbors import BallTree, DistanceMetric
>>> 
>>> texts = ["Some string", "Some other string", "Yet another string"]
>>> query = "Smeo srting"
>>> knn = 2
>>> 
>>> def text_to_vector(text: str, idx: Optional[int] = None) -> np.ndarray:
..     if idx is None:
..         idx = len(texts)
..         texts.append(text)
..     return np.array([idx], dtype=np.float64)
.. 
>>> def vector_to_text(idx: np.ndarray) -> str:
..     return texts[int(idx[0])]
.. 
>>> def levdist(x: np.ndarray, y: np.ndarray) -> int:
..     x, y = map(vector_to_text, (x, y))
..     return Levenshtein.distance(x, y)
.. 
>>> X = [text_to_vector(text, idx) for idx, text in enumerate(texts)]
>>> x = [text_to_vector(query)]
>>> 
>>> tree = BallTree(X, metric=DistanceMetric.get_metric('pyfunc', func=levdist))
>>> (dists,), (idxs,) = tree.query(x, k=knn)
>>> for dist, idx in zip(dists, idxs):
..    print(f'{texts[idx]}, {int(dist)}')
.. 
Some string, 4
Some other string, 8

0

Việc triển khai đệ quy này rất kém hiệu quả vì nó tính toán lại khoảng cách Levenshtein của cùng một chuỗi con nhiều lần. Chúng tôi đếm số lượng cuộc gọi trong phiên bản sau bằng cách sử dụng chức năng trang trí. Nếu bạn không biết chúng, bạn có thể tìm hiểu về chúng trong chương của chúng tôi về Ghi nhớ và Trang trí

$ pip install sklearn python-Levenshtein
$ python
>>> from typing import Optional
>>> import Levenshtein
>>> import numpy as np
>>> from sklearn.neighbors import BallTree, DistanceMetric
>>> 
>>> texts = ["Some string", "Some other string", "Yet another string"]
>>> query = "Smeo srting"
>>> knn = 2
>>> 
>>> def text_to_vector(text: str, idx: Optional[int] = None) -> np.ndarray:
..     if idx is None:
..         idx = len(texts)
..         texts.append(text)
..     return np.array([idx], dtype=np.float64)
.. 
>>> def vector_to_text(idx: np.ndarray) -> str:
..     return texts[int(idx[0])]
.. 
>>> def levdist(x: np.ndarray, y: np.ndarray) -> int:
..     x, y = map(vector_to_text, (x, y))
..     return Levenshtein.distance(x, y)
.. 
>>> X = [text_to_vector(text, idx) for idx, text in enumerate(texts)]
>>> x = [text_to_vector(query)]
>>> 
>>> tree = BallTree(X, metric=DistanceMetric.get_metric('pyfunc', func=levdist))
>>> (dists,), (idxs,) = tree.query(x, k=knn)
>>> for dist, idx in zip(dists, idxs):
..    print(f'{texts[idx]}, {int(dist)}')
.. 
Some string, 4
Some other string, 8

1

ĐẦU RA

$ pip install sklearn python-Levenshtein
$ python
>>> from typing import Optional
>>> import Levenshtein
>>> import numpy as np
>>> from sklearn.neighbors import BallTree, DistanceMetric
>>> 
>>> texts = ["Some string", "Some other string", "Yet another string"]
>>> query = "Smeo srting"
>>> knn = 2
>>> 
>>> def text_to_vector(text: str, idx: Optional[int] = None) -> np.ndarray:
..     if idx is None:
..         idx = len(texts)
..         texts.append(text)
..     return np.array([idx], dtype=np.float64)
.. 
>>> def vector_to_text(idx: np.ndarray) -> str:
..     return texts[int(idx[0])]
.. 
>>> def levdist(x: np.ndarray, y: np.ndarray) -> int:
..     x, y = map(vector_to_text, (x, y))
..     return Levenshtein.distance(x, y)
.. 
>>> X = [text_to_vector(text, idx) for idx, text in enumerate(texts)]
>>> x = [text_to_vector(query)]
>>> 
>>> tree = BallTree(X, metric=DistanceMetric.get_metric('pyfunc', func=levdist))
>>> (dists,), (idxs,) = tree.query(x, k=knn)
>>> for dist, idx in zip(dists, idxs):
..    print(f'{texts[idx]}, {int(dist)}')
.. 
Some string, 4
Some other string, 8

2

Chúng ta có thể thấy rằng hàm đệ quy này rất kém hiệu quả. Khoảng cách Levenshtein của chuỗi s="" và t="P" được tính 5336 lần. Trong phiên bản sau, chúng tôi thêm một số "bộ nhớ" vào hàm Levenshtein đệ quy của mình bằng cách thêm một bản ghi nhớ từ điển

>>> s = "Manhatan"
>>> s = s[:5] + "t" + s[5:]
>>> print(s)
Manhattan

0

ĐẦU RA

>>> s = "Manhatan"
>>> s = s[:5] + "t" + s[5:]
>>> print(s)
Manhattan

1

Phiên bản đệ quy trước đó hiện đã hiệu quả, nhưng nó có lỗi thiết kế trong đó. Chúng tôi đã làm ô nhiễm mã bằng các câu lệnh để cập nhật bộ nhớ từ điển của chúng tôi. Tất nhiên, thiết kế sẽ tốt hơn rất nhiều, nếu chúng ta không làm ô nhiễm mã của mình bằng cách thêm logic để lưu các giá trị vào hàm Levenshtein của chúng ta. Chúng tôi cũng có thể "thuê ngoài" mã này thành một công cụ trang trí. Phiên bản sau sử dụng trình trang trí "ghi nhớ" để lưu các giá trị này

>>> s = "Manhatan"
>>> s = s[:5] + "t" + s[5:]
>>> print(s)
Manhattan

2

ĐẦU RA

>>> s = "Manhatan"
>>> s = s[:5] + "t" + s[5:]
>>> print(s)
Manhattan

3

Các cuộc gọi bổ sung đến từ thực tế là chúng ta có ba cuộc gọi vô điều kiện làm đối số của hàm "min"

Tính toán lặp lại khoảng cách Levenshtein

Để tính toán khoảng cách Levenshtein theo cách không đệ quy, chúng tôi sử dụng ma trận chứa khoảng cách Levenshtein giữa tất cả các tiền tố của chuỗi đầu tiên và tất cả các tiền tố của chuỗi thứ hai. Chúng ta có thể tự động tính toán các giá trị trong ma trận này. Giá trị cuối cùng được tính sẽ là khoảng cách giữa hai chuỗi đầy đủ. Đây là một ví dụ về thuật toán của lập trình động từ dưới lên

Thuật toán hoạt động như thế này.
Chúng tôi đặt chi phí cho một lần chèn, xóa và thay thế thành 1. Chúng tôi muốn tính khoảng cách giữa hai chuỗi s và t với len(s) == m và len(t) == n. Một ma trận D được sử dụng, chứa trong ô (i,j) khoảng cách Levenshtein giữa s[. i+1] và t[. j+1]. Các giá trị của ma trận sẽ được tính bắt đầu từ góc trên bên trái và kết thúc ở góc dưới bên phải.

Chúng tôi bắt đầu với việc điền vào các trường hợp cơ bản, tôi. e. hàng và cột có chỉ số 0. Tính toán trong trường hợp này có nghĩa là chúng ta điền vào hàng có chỉ số 0 với độ dài của các chuỗi con là t và tương ứng điền vào cột có chỉ số 0 với độ dài của các chuỗi con là s

Giá trị của tất cả các phần tử khác của ma trận chỉ phụ thuộc vào giá trị của hàng xóm bên trái, hàng xóm trên cùng và hàng xóm trên cùng bên trái của chúng

Việc tính toán D(i,j) cho cả i và j lớn hơn 0 hoạt động như thế này. D(i,j) có nghĩa là chúng ta đang tính khoảng cách Levenshtein của các chuỗi con s[0. i-1] và t[0. j-1]. Nếu các ký tự cuối cùng của các chuỗi con này bằng nhau, khoảng cách chỉnh sửa tương ứng với khoảng cách của các chuỗi con s[0. -1] và t[0. -1], có thể trống nếu s hoặc t chỉ bao gồm một ký tự, nghĩa là chúng ta sẽ sử dụng các giá trị từ cột hoặc hàng thứ 0. Nếu các ký tự cuối cùng của s[0. i-1] và t[0. j-1] không bằng nhau, khoảng cách chỉnh sửa D[i,j] sẽ được đặt thành tổng của 1 + min(D[i, j-1], D[i-1, j], D[i-

Chúng tôi minh họa điều này trong sơ đồ sau

>>> s = "Manhatan"
>>> s = s[:5] + "t" + s[5:]
>>> print(s)
Manhattan

4

ĐẦU RA

>>> s = "Manhatan"
>>> s = s[:5] + "t" + s[5:]
>>> print(s)
Manhattan

5

Hình ảnh sau đây về ma trận của phép tính trước đây của chúng tôi chứa - được tô màu vàng - đường đi tối ưu qua ma trận. Chúng tôi bắt đầu bằng việc xóa ("f"), chúng tôi giữ "l" (không tính thêm chi phí), sau đó, chúng tôi giữ "a" và "w". Bước cuối cùng là chèn, tăng chi phí lên 2, là khoảng cách Levenstein cuối cùng

Vì lợi ích của một ví dụ khác, chúng ta hãy sử dụng khoảng cách Levenshtein cho ví dụ đầu tiên của chương này. Vì vậy, chúng ta hầu như sẽ "quay trở lại" thành phố New York và quận Manhattan ly kỳ của nó. Chúng tôi so sánh nó với lỗi chính tả "Manahaton", là sự kết hợp của nhiều lỗi chính tả phổ biến khác nhau

>>> s = "Manhatan"
>>> s = s[:5] + "t" + s[5:]
>>> print(s)
Manhattan

6

ĐẦU RA

>>> s = "Manhatan"
>>> s = s[:5] + "t" + s[5:]
>>> print(s)
Manhattan

7

Cho đến nay, chúng tôi đã có chi phí cố định cho việc thêm, xóa và thay thế, tôi. e. mỗi người trong số họ được đặt thành 1

 

>>> s = "Manhatan"
>>> s = s[:5] + "t" + s[5:]
>>> print(s)
Manhattan

8

ĐẦU RA

>>> s = "Manhatan"
>>> s = s[:5] + "t" + s[5:]
>>> print(s)
Manhattan

9

Tình huống trong lệnh gọi iterative_levenshtein với chi phí mặc định, tôi. e. 1 để chèn, xóa và thay thế

Nội dung của ma trận nếu chúng ta thay thế đắt gấp đôi so với chèn và xóa, i. e. cuộc gọi iterative_levenshtein("abc", "xyz", cost=(1, 1, 2))

Bây giờ chúng tôi gọi iterative_levenshtein("abc", "xyz", cost=(2, 2, 1)), có nghĩa là một lần thay thế chỉ bằng một nửa so với một lần chèn hoặc xóa

Cũng có thể có trọng số riêng cho từng ký tự. Thay vì chuyển một bộ có ba giá trị cho hàm, chúng ta sẽ sử dụng một từ điển với các giá trị cho mỗi ký tự

>>> s = "Mannhattan"
>>> s = s[:2] + s[3:]
>>> s
'Manhattan'

0

ĐẦU RA

>>> s = "Mannhattan"
>>> s = s[:2] + s[3:]
>>> s
'Manhattan'

1

Chúng tôi chứng minh trong sơ đồ sau đây cách thuật toán hoạt động với các ký tự có trọng số. Mũi tên màu cam hiển thị đường dẫn đến khoảng cách chỉnh sửa tối thiểu 11

 

Đào tạo Python trực tiếp

Thưởng thức trang này?

Nhìn thấy. Tổng quan về các khóa học Python trực tiếp

đăng ký tại đây

chú thích

1 Đo lường sự giống nhau trong âm nhạc. Một cách tiếp cận định lượng cho các biểu diễn phi tham số, Orpen, K. , & Huron, D. (1992)