Làm thế nào để bình thường hóa khoảng cách Levenshtein cho chiều dài liên kết tối đa thay vì chiều dài chuỗi?

Question

Vấn đề: Một vài gói R có tính năng triển khai khoảng cách Levenshtein để tính toán sự giống nhau của hai chuỗi, ví dụ: http://finzi.psych.upenn.edu/R/library/RecordLinkage/html/strcmp.html. Khoảng cách được tính có thể dễ dàng được chuẩn hóa cho độ dài chuỗi, ví dụ: bằng cách chia khoảng cách Levenshtein theo chiều dài của chuỗi dài nhất có liên quan hoặc bằng cách chia nó bằng giá trị trung bình của độ dài của hai chuỗi. Đối với một số ứng dụng trong ngôn ngữ học (ví dụ: đo lường và nghiên cứu đa ngôn ngữ tiếp thu), chúng tôi đề nghị khoảng cách Levenshtein thô được chuẩn hóa theo chiều dài của liên kết chi phí ít nhất dài nhất (Heeringa, 2004: 130-132). Điều này có xu hướng tạo ra các biện pháp khoảng cách có ý nghĩa hơn từ quan điểm nhận thức ngôn ngữ.

Ví dụ: Chuỗi Đức "tsYklUs" (Zyklus = chu kỳ) có thể được chuyển đổi thành cùng nguồn gốc Thụy Điển của nó "sYkEl" (cyckel = (bi) chu kỳ) trong một sự liên kết 7-khe với hai chèn (I) và hai thay thế (S) với tổng chi phí biến đổi của 4. Bình thường khoảng cách levenshtein: 4/7

(A)

t--s--Y--k--l--U--s 
---s--Y--k--E--l--- 
=================== 
I-----------S--S--I = 4 

Nó cũng có thể chuyển đổi các chuỗi trong một sự liên kết 8 khe với 3 lần chèn (I) và 1 lần xóa (D), cũng cho tổng chi phí căn chỉnh là 4. Bình thường khoảng cách levenshtein: 4/8

(B)

t--s--Y--k-----l--U--S 
---s--Y--k--E--l------ 
====================== 
I-----------D-----I--I = 4 

Các liên kết thứ hai có ý nghĩa hơn ngôn ngữ, bởi vì nó gắn các [l] -phonemes với nhau hơn là với [E] và [U] nguyên âm.

Câu hỏi: Có ai biết về bất kỳ chức năng R mà sẽ cho phép tôi để bình thường hóa khoảng cách Levenshtein cho sự liên kết chi phí thấp nhất dài nhất chứ không phải là cho chiều dài chuỗi thích hợp? Cảm ơn bạn đã nhập!

Tham chiếu: W.J. Heeringa (2004), Đo lường cách phát âm của phương ngữ bằng cách sử dụng khoảng cách Levenshtein. Luận án tiến sĩ, Đại học Groningen. http://www.let.rug.nl/~heeringa/dialectology/thesis/

Chỉnh sửa - Giải pháp: Tôi nghĩ rằng tôi đã tìm ra giải pháp. Chức năng adist có thể trả về căn chỉnh và dường như là mặc định cho căn chỉnh chi phí thấp nhất dài nhất.Để mất ví dụ trên, đây là sự liên kết gắn liền với sykel-tsyklus:

> attr(adist("sykel", "tsyklus", counts = TRUE), "trafos") 
    [,1]  
[1,] "IMMMDMII" 

để tính toán khoảng cách chiều dài-bình thường theo khuyến cáo của Heeringa (2004), chúng ta có thể viết một hàm khiêm tốn:

normLev.fnc <- function(a, b) { 
    drop(adist(a, b)/nchar(attr(adist(a, b, counts = TRUE), "trafos"))) 
} 

Đối với ví dụ trên, này trả

> normLev.fnc("sykel", "tsyklus") 
[1] 0.5 

chức năng này một LSO trả về khoảng cách bình thường hóa chính xác cho Heeringa (2004: 131) ví dụ:

> normLev.fnc("bine", "bEi") 
[1] 0.6 
> normLev.fnc("kaninçen", "konEin") 
[1] 0.5555556 
> normLev.fnc("kenEeri", "kenArje") 
[1] 0.5 

Để so sánh một số cặp dây:

> L1 <- c("bine", "kaninçen", "kenEeri") 
> L2 <- c("bEi", "konEin", "kenArje") 
> diag(normLev.fnc(L1, L2)) 
[1] 0.6000000 0.5555556 0.5000000 

Answer 1

Trong mọi trường hợp nhà ngôn ngữ học vấp ngã khi bài này, tôi muốn chỉ ra rằng các thuật toán được cung cấp bởi gói RecordLinkage không nhất thiết phải tối ưu để so sánh các chuỗi không phải ASCII, ví dụ:

> levenshteinSim("väg", "way") 
[1] -0.3333333 
> levenshteinDist("väg", "way") 
[1] 4 
> levenshteinDist("väg", "wäy") 
[1] 2 
> levenshteinDist("väg", "wüy") 
[1] 3