Tính khoảng cách Levenshtein tương đối - có ý nghĩa?

Question

Tôi đang sử dụng cả hai Daitch-Mokotoff soundexing và Damerau-Levenshtein để tìm hiểu xem một mục nhập người dùng và một giá trị trong ứng dụng là "giống nhau" hay không.

Khoảng cách Levenshtein có được sử dụng như một giá trị tuyệt đối không? Nếu tôi có một từ 20 chữ cái, khoảng cách 4 không quá tệ. Nếu từ này có 4 chữ cái ...

Điều tôi đang làm là lấy khoảng cách/chiều dài để có khoảng cách phản ánh tốt hơn phần trăm của từ đã được thay đổi.

Đó có phải là cách tiếp cận hợp lệ/đã được chứng minh không? Hay là nó ngu ngốc?

Answer 1

Khoảng cách Levenshtein được coi là được sử dụng làm giá trị tuyệt đối?

Dường như nó sẽ tùy thuộc vào yêu cầu của bạn. (Để làm rõ: Levenshtein khoảng cách là giá trị tuyệt đối, nhưng như OP chỉ ra, giá trị thô có thể không hữu ích như đối với một ứng dụng nhất định làm thước đo tính theo chiều dài của từ đó. đang thực sự quan tâm nhiều hơn trong tương hơn khoảng cách cho mỗi gia nhập.)

tôi đang sử dụng cả hai Daitch-Mokotoff soundexing và Damerau-Levenshtein để tìm hiểu xem một mục người dùng và một giá trị trong việc áp dụng là "giống ".

Có vẻ như bạn đang cố gắng xác định xem người dùng có ý định mục nhập của họ giống với giá trị dữ liệu nhất định không?

Bạn có đang kiểm tra chính tả không? hoặc phù hợp với đầu vào không hợp lệ cho một tập hợp các giá trị đã biết? Ưu tiên của bạn là gì?

• Minimize dương tính giả (cố gắng đảm bảo tất cả các từ gợi ý rất "tương tự", và danh sách gợi ý là ngắn)
• Minimize âm tính giả (cố gắng đảm bảo rằng chuỗi người dùng dự định là trong danh sách đề nghị, ngay cả khi nó làm cho danh sách dài)
• Tối đa hóa khớp lệnh trung bình chính xác

Bạn có thể kết thúc bằng khoảng cách Levenshtein trong cách này để xác định xem một từ nên được cung cấp trong một danh sách gợi ý; và một cách khác để xác định cách đặt hàng danh sách đề xuất. Có vẻ như với tôi, nếu tôi suy ra mục đích của bạn một cách chính xác, điều cốt lõi bạn muốn đo là giống nhau hơn là sự khác biệt giữa hai chuỗi. Như vậy, bạn có thể sử dụng Jaro or Jaro-Winkler distance, trong đó có tính đến chiều dài của chuỗi và số ký tự chung:

Các Jaro khoảng cách dj hai cho chuỗi s1 và s2 là

(m/|s1| + m/|s2| + (m - t)/m)/3 

nơi:

• m là số lượng phù hợp với nhân vật
• t là số transpositions

Jaro-Winkler khoảng cách sử dụng một tiền tố quy mô p mang đến cho thuận lợi hơn xếp hạng thành các chuỗi phù hợp với từ bắt đầu cho một chiều dài bộ tiền tố l.

Answer 2

Khoảng cách levenshtein là giá trị tương đối giữa hai từ. So sánh LD với độ dài không phải là ví dụ liên quan

mèo -> SCAT = 1 (75% tương tự ??)

chênh lệch -> sự khác biệt = 1 (90% tương tự ??)

Cả hai từ có khoảng cách lev của 1 nghĩa là chúng khác nhau bởi một ký tự, nhưng khi so sánh với độ dài của chúng, tập thứ hai sẽ có vẻ 'tương tự' hơn.

tôi sử dụng soundexing để xếp hạng từ mà có cùng khoảng cách lev ví dụ

cat và fat cả hai đều có một LD trong tổng số 1 tương ứng với kat, nhưng từ đó nhiều khả năng được kat hơn chất béo khi sử dụng Soundex (giả sử từ được viết sai chính tả, không được gõ sai!)

Vì vậy, câu trả lời ngắn chỉ là sử dụng khoảng cách lev để xác định sự giống nhau.