วิธีการคำนวณระยะทาง levenshtein ใน python

ระยะห่างของ Levenshtein ระหว่างสองสายคือจำนวนขั้นต่ำของการเปลี่ยนแปลงอักขระเดี่ยวที่จำเป็นในการแปลงคำหนึ่งเป็นอีกคำหนึ่ง

คำว่า “การแก้ไข” รวมถึงการแทนที่ การแทรก และการลบ

ตัวอย่างเช่น สมมติว่าเรามีคำสองคำต่อไปนี้:

• เพื่อปาร์ตี้
• สวน

ระยะห่างของ Levenshtein ระหว่างสองคำ (เช่น จำนวนการเปลี่ยนแปลงที่เราต้องทำเพื่อแปลงคำหนึ่งเป็นอีกคำหนึ่ง) จะเป็น 2 :

ในทางปฏิบัติ ระยะทางของ Levenshtein ถูกนำมาใช้ในการใช้งานต่างๆ มากมาย รวมถึงการจับคู่สตริงแบบคลุมเครือ การตรวจสอบตัวสะกด และการประมวลผลภาษาธรรมชาติ

บทช่วยสอนนี้จะอธิบายวิธีคำนวณระยะห่างของ Levenshtein ระหว่างสตริงใน Python โดยใช้โมดูล python-Levenshtein

คุณสามารถใช้ไวยากรณ์ต่อไปนี้เพื่อติดตั้งโมดูลนี้:

 pip install python-Levenshtein

จากนั้นคุณสามารถโหลดฟังก์ชันเพื่อคำนวณระยะทางเลเวนชไทน์ได้:

 from Levenshtein import distance as lev

ตัวอย่างต่อไปนี้แสดงวิธีใช้ฟังก์ชันนี้ในทางปฏิบัติ

ตัวอย่างที่ 1: ระยะห่างของ Levenshtein ระหว่างสองสาย

รหัสต่อไปนี้แสดงวิธีการคำนวณระยะทาง Levenshtein ระหว่างสองสาย “party” และ “park”:

 #calculate Levenshtein distance
lev(' party ', ' park ')

2

ระยะทางเลเวนชไตน์กลายเป็น 2

ตัวอย่างที่ 2: ระยะห่างของ Levenshtein ระหว่างสองตาราง

รหัสต่อไปนี้แสดงวิธีการคำนวณระยะทาง Levenshtein ระหว่างแต่ละคู่ของสตริงในอาร์เรย์ที่แตกต่างกันสองชุด:

 #define arrays
a = ['Mavs', 'Spurs', 'Lakers', 'Cavs']
b <- ['Rockets', 'Pacers', 'Warriors', 'Celtics']

#calculate Levenshtein distance between two arrays
for i,k in zip (a,b):
  print (lev(i, k))

6
4
5
5

วิธีการตีความผลลัพธ์มีดังนี้:

• ระยะห่างของ Levenshtein ระหว่าง “Mavs” และ “Rockets” คือ 6
• ระยะห่างของเลเวนชไตน์ระหว่าง “สเปอร์ส” และ “เพเซอร์ส” คือ 4
• ระยะห่างของเลเวนชไทน์ระหว่าง “เลเกอร์ส” และ “นักรบ” คือ 5
• ระยะห่างของเลเวนชไทน์ระหว่าง “แคฟส์” และ “เซลติกส์” คือ 5

แหล่งข้อมูลเพิ่มเติม

วิธีการคำนวณระยะทางแฮมมิงใน Python
วิธีการคำนวณระยะทางแบบยุคลิดใน Python
วิธีการคำนวณระยะทาง Mahalanobis ใน Python