วิธีการคำนวณระยะทาง levenshtein ใน r (พร้อมตัวอย่าง)

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

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

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

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

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

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

บทช่วยสอนนี้จะอธิบายวิธีคำนวณระยะห่างของ Levenshtein ระหว่างสตริงใน R โดยใช้ฟังก์ชัน stringdist() ของแพ็คเกจ stringdist ใน R

ฟังก์ชันนี้ใช้ไวยากรณ์พื้นฐานต่อไปนี้:

 #load stringdist package
library(stringdist)

#calculate Levenshtein distance between two strings
stringdist(" string1 ", " string2 ", method = " lv ")

โปรดทราบว่าฟังก์ชันนี้สามารถคำนวณการวัดระยะทางต่างๆ ได้มากมาย โดยการระบุ method = “lv” เราจะบอกฟังก์ชันให้คำนวณระยะทางเลเวนชไทน์

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

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

 #load stringdist package
library(stringdist)

#calculate Levenshtein distance between two strings
stringdist(' party ', ' park ', method = ' lv ')

[1] 2

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

ตัวอย่างที่ 2: ระยะห่างของเลเวนชไทน์ระหว่างเวกเตอร์สองตัว

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

 #load stringdist package
library(stringdist)

#definevectors
a <- c('Mavs', 'Spurs', 'Lakers', 'Cavs')
b <- c('Rockets', 'Pacers', 'Warriors', 'Celtics')

#calculate Levenshtein distance between two vectors
stringdist(a, b, method=' lv ')

[1] 6 4 5 5

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

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

ตัวอย่างที่ 3: ระยะห่างของเลเวนชไทน์ระหว่างคอลัมน์ของกรอบข้อมูล

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

 #load stringdist package
library(stringdist)

#define data
data <- data.frame(a = c('Mavs', 'Spurs', 'Lakers', 'Cavs'),
                   b = c('Rockets', 'Pacers', 'Warriors', 'Celtics'))

#calculate Levenshtein distance
stringdist(data$a, data$b, method=' lv ')

[1] 6 4 5 5

จากนั้นเราสามารถเพิ่มระยะทาง Levenshtein เป็นคอลัมน์ใหม่ในกรอบข้อมูลได้หากเราต้องการ:

 #save Levenshtein distance as vector
lev <- stringdist(data$a, data$b, method=' lv ')

#append Levenshtein distance as new column
data$lev <- lev

#view data frame
data

       ab lev
1 Mavs Rockets 6
2 Spurs Pacers 4
3 Lakers Warriors 5
4 Cavs Celtics 5

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

วิธีการคำนวณระยะทาง Hamming ใน R
วิธีการคำนวณระยะทางแบบยุคลิดในหน่วย R
วิธีการคำนวณระยะทางจากแมนฮัตตันในอาร์