Tương tự về chuỗi -> Khoảng cách Levenshtein

Question

Tôi đang sử dụng thuật toán Levenshtein để tìm sự giống nhau giữa hai chuỗi. Đây là một phần rất quan trọng của chương trình tôi đang làm, vì vậy nó cần phải có hiệu quả. Vấn đề là các thuật toán không tìm thấy các ví dụ sau đây là tương tự:

Conair
AIRCON

Thuật toán sẽ cung cấp cho khoảng cách 6. Vì vậy, cho từ này của 6 chữ cái (Bạn nhìn vào từ có số lượng chữ cái cao nhất), chênh lệch là 100% => mức tương tự là 0%.

Tôi cần tìm cách để tìm điểm giống nhau giữa hai chuỗi, nhưng cũng xem xét các trường hợp giống như trường hợp tôi đã trình bày trước đây.

Có thuật toán tốt hơn tôi có thể sử dụng không? Hoặc các bạn giới thiệu cho tôi điều gì?

EDIT: Tôi cũng đã xem xét thuật toán "Damerau – Levenshtein", bổ sung thêm các chuyển vị. Vấn đề là chuyển đổi này chỉ dành cho các ký tự liền kề (và không phải cho một số ký tự).

Answer 1

Tôi sẽ chia cụm từ thành unigrams, bigrams và trigram, sau đó tính độ tương tự cosin.

Answer 2

Có vẻ như bạn có thể muốn thử thực hiện khoảng cách Levenshtein bằng âm tiết hoặc âm vị thay vì chữ cái.

Answer 3

Về mặt lý thuyết, cách tiếp cận bạn đang sử dụng là chính xác cho sự cố bạn đang cố giải quyết. Nhưng Levenstein sẽ chỉ xem xét các nhân vật riêng lẻ mà hai bộ.

Tương tự chuỗi cũng có thể được tìm thấy bằng phương pháp Longest Common Subsequence và sau đó bạn có thể thấy Levenstein trên phần còn lại của chưa từng có.

Trong trường hợp bạn muốn thực hiện một cách tiếp cận theo nhóm, the following answer dường như có một số chi tiết, nhưng rõ ràng là khó thực hiện hơn.

Answer 4

Sắp xếp các từ và tìm Levenshtein sẽ cho kết quả phù hợp 100% cho ví dụ của bạn nhưng nó cũng sẽ cho kết quả phù hợp 100%, ví dụ:

CONAIR 
RCIAON 

có thể không phải là thứ bạn muốn.

Cách khác để xác định sự giống nhau là tìm ra các chất nền chung cho 2 chuỗi. Bạn có thể tạo một Suffix Tree và tìm hiểu tất cả các chất nền phổ biến và cố gắng xác định chúng giống nhau như thế nào. Vì vậy, ví dụ: cây hậu tố sẽ cung cấp các chất nền chung như CON & AIR bao gồm toàn bộ từ (cho 2 dây của bạn) và do đó kết luận chúng giống nhau.

Answer 5

Tôi nghĩ rằng điều này có thể dễ dàng được giải quyết bằng cách sử dụng thuật toán Dài nhất Chuỗi con/Tiếp theo trên một trong các chuỗi (ví dụ "conair") và chuỗi khác nối vào chính nó một lần (ví dụ: "aircon" -> "airconaircon ").

Mẫu mã trong C:

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 

// Returns the length of the longest common substring (LCS) 
// between two given strings. 
// 
// This recursive implementation can be replaced by a 
// more performant dynamic programming implementation. 
size_t llcs(const char* s1, const char* s2) 
{ 
    size_t len[3]; 

    if (*s1 == '\0' || *s2 == '\0') return 0; 

    len[0] = (*s1 == *s2) + llcs(s1 + 1, s2 + 1); 
    len[1] = llcs(s1 + 1, s2); 
    len[2] = llcs(s1, s2 + 1); 

    if (len[0] < len[1]) len[0] = len[1]; 
    if (len[0] < len[2]) len[0] = len[2]; 

    return len[0]; 
} 

// Returns similarity of two given strings in the range 
// from 0.0 to 1.0 (1.0 for equal strings). 
double similarity(const char* s1, const char* s2) 
{ 
    size_t s1len = strlen(s1); 
    size_t s2len = strlen(s2); 
    double sim; 

    if (s1len == 0 && s2len == 0) 
    { 
    // Two empty strings are equal 
    sim = 1; 
    } 
    else 
    { 
    size_t len; 
    // Append s1 to itself in s1s1 (e.g. "aircon" -> "airconaircon") 
    char* s1s1 = malloc(s1len * 2 + 1); 
    strcpy(s1s1, s1); 
    strcpy(s1s1 + s1len, s1); 

    // Find the length of the LCS between s1s1 and s2 
    // (e.g. between "airconaircon" and "conair") 
    len = llcs(s1s1, s2); 
    // We need it not longer than s1 (e.g. "aircon") 
    // since we're actually comparing s1 and s2 
    if (len > s1len) len = s1len; 

    len *= 2; 

    // Prevent 100% similarity between a string and its 
    // cyclically shifted version (e.g. "aircon" and "conair") 
    if (len == s1len + s2len && strcmp(s1, s2) != 0) len--; 

    // Get the final measure of the similarity 
    sim = (double)len/(s1len + s2len); 

    free(s1s1); 
    } 

    return sim; 
} 

int main(int argc, char** argv) 
{ 
    if (argc == 3) 
    printf("Similarity of \"%s\" and \"%s\" is %.2f%%\n", 
      argv[1], argv[2], 100 * similarity(argv[1], argv[2])); 
    else 
    printf("Usage:\n %s string1 string2\n", 
      argv[0]); 
    return 0; 
} 

Mẫu đầu ra:

Similarity of "123" and "123" is 100.00% 
Similarity of "123" and "1234" is 85.71% 
Similarity of "0123" and "123" is 85.71% 
Similarity of "a" and "aa" is 66.67% 
Similarity of "aa" and "a" is 66.67% 
Similarity of "aaaaaaa" and "aaaaaa" is 92.31% 
Similarity of "aaaaaa" and "aaaaaaa" is 92.31% 
Similarity of "aircon" and "conair" is 91.67% 
Similarity of "spit" and "pits" is 87.50% 
Similarity of "pits" and "spit" is 87.50% 
Similarity of "spits" and "pits" is 88.89% 
Similarity of "pits" and "spits" is 88.89% 

Answer 6

Hãy xem để Needleman-Wunsch, hoặc các thuật toán Smith-Waterman. Chúng được sử dụng để xử lý chuỗi phù hợp thông qua chỉnh sửa khoảng cách chỉnh sửa cho chuỗi DNA, nơi bất kỳ loại chèn, đảo ngược, transposons có thể xảy ra, với bất kỳ chiều dài, tại bất kỳ nơi nào. Nói điều này, tôi cần phải thêm rằng cho một chuỗi đủ dài không có giải pháp tối ưu. Và đừng quên rằng chi phí chỉnh sửa phụ thuộc vào ngữ cảnh sử dụng của thuật toán (một vấn đề ngữ nghĩa), trong khi bất kỳ thuật toán nào cũng luôn là một máy cú pháp.

Answer 7

thử sử dụng các biện pháp tương tự khác như Sorenson, Jaccard và jaro_winkler

cá nhân tôi là fan hâm mộ lớn của Jaro Winkler vì nó phục vụ mục đích nhiều lần tôi.

from Levenshtein import jaro_winkler 
In [2]: jaro_winkler("conair","aircon") 
Out[2]: 0.8333333333333334