Thực hiện khoảng cách Levenshtein cho tìm kiếm mysql/mờ?

Question

Tôi muốn có thể tìm kiếm một bảng như sau cho smith như nhận được tất cả mọi thứ mà nó trong vòng 1 phương sai.

dữ liệu:

 
O'Brien 
Smithe 
Dolan 
Smuth 
Wong 
Smoth 
Gunther 
Smiht 

tôi đã nhìn vào sử dụng khoảng cách levenshtein không ai biết làm thế nào để thực hiện điều này với nó?

Answer 1

Điều này có hữu ích không? MySQL Levenshtein distance query

EDIT: Liên kết cũ Levenshtein Distance as a MySQL stored function (Google Cache) bị hỏng, nhờ Robert đã chỉ ra điều này trong nhận xét.

EDIT2: Cả hai liên kết bị phá vỡ, sử dụng this one

Answer 2

Để tìm kiếm hiệu quả sử dụng khoảng cách Levenshtein, bạn cần một, chỉ số chuyên môn hiệu quả, chẳng hạn như một bk-tree. Thật không may, không có hệ thống cơ sở dữ liệu tôi biết, bao gồm cả MySQL, thực hiện các chỉ mục bk-tree. Điều này phức tạp hơn nếu bạn đang tìm kiếm tìm kiếm toàn văn, thay vì chỉ một cụm từ trên mỗi hàng. Off-hand, tôi không thể nghĩ ra cách nào để bạn có thể lập chỉ mục toàn văn theo cách cho phép tìm kiếm dựa trên khoảng cách levenshtein.

Answer 3

Việc thực hiện khoảng cách damerau-levenshtein có thể tìm thấy tại đây: Damerau-Levenshtein algorithm: Levenshtein with transpositions Cải thiện trên khoảng cách Levenshtein thuần túy là việc trao đổi các ký tự được xem xét. Tôi tìm thấy nó trong các ý kiến ​​của liên kết của schnaader, cảm ơn!

Answer 4

tôi đang thiết lập một tìm kiếm dựa trên Levenshtein hoặc Damerau-Levenshtein (có lẽ sau này) cho tìm kiếm nhiều hơn một văn bản được lập chỉ mục, dựa trên một bài báo của Gonzalo Navarro và Ricardo Baeza-yates: link text

Sau xây dựng một mảng hậu tố (see wikipedia), nếu bạn quan tâm đến một chuỗi có nhiều nhất m không khớp với chuỗi tìm kiếm, hãy chia chuỗi tìm kiếm thành k + 1 miếng; ít nhất một trong số đó phải còn nguyên vẹn. Tìm các chất nền bằng cách tìm kiếm nhị phân trên mảng hậu tố, sau đó áp dụng hàm khoảng cách cho miếng vá xung quanh từng mảnh phù hợp.

Answer 5

bạn có thể sử dụng chức năng này

 

CREATE FUNCTION `levenshtein`(s1 text, s2 text) RETURNS int(11) 
    DETERMINISTIC 
BEGIN 
    DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT; 
    DECLARE s1_char CHAR; 
    DECLARE cv0, cv1 text; 
    SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0; 
    IF s1 = s2 THEN 
     RETURN 0; 
    ELSEIF s1_len = 0 THEN 
     RETURN s2_len; 
    ELSEIF s2_len = 0 THEN 
     RETURN s1_len; 
    ELSE 
     WHILE j <= s2_len DO 
     SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1; 
     END WHILE; 
     WHILE i <= s1_len DO 
     SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1; 
     WHILE j <= s2_len DO 
      SET c = c + 1; 
      IF s1_char = SUBSTRING(s2, j, 1) THEN 
      SET cost = 0; ELSE SET cost = 1; 
      END IF; 
      SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost; 
      IF c > c_temp THEN SET c = c_temp; END IF; 
      SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1; 
      IF c > c_temp THEN 
       SET c = c_temp; 
      END IF; 
      SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1; 
     END WHILE; 
     SET cv1 = cv0, i = i + 1; 
     END WHILE; 
    END IF; 
    RETURN c; 
    END 

và để có được nó như XX% sử dụng chức năng này

 

CREATE FUNCTION `levenshtein_ratio`(s1 text, s2 text) RETURNS int(11) 
    DETERMINISTIC 
BEGIN 
    DECLARE s1_len, s2_len, max_len INT; 
    SET s1_len = LENGTH(s1), s2_len = LENGTH(s2); 
    IF s1_len > s2_len THEN 
     SET max_len = s1_len; 
    ELSE 
     SET max_len = s2_len; 
    END IF; 
    RETURN ROUND((1 - LEVENSHTEIN(s1, s2)/max_len) * 100); 
    END 

Answer 6

Tôi đã có một trường hợp đặc biệt của k-khoảng cách tìm kiếm và sau khi cài đặt Damerau-Levenshtein UDF trong MySQL nhận thấy rằng truy vấn mất quá nhiều thời gian. Tôi đã đưa ra giải pháp sau:

• Tôi có một không gian tìm kiếm rất hạn chế (chuỗi ký tự 9 được giới hạn ở giá trị số).

Tạo bảng mới (hoặc nối thêm cột vào bảng mục tiêu) với cột cho từng vị trí ký tự trong trường mục tiêu của bạn. I E. VARCHAR của tôi (9) đã kết thúc dưới dạng 9 cột TINYINT + 1 cột Id khớp với bảng chính của tôi (thêm chỉ mục cho mỗi cột). Tôi đã thêm trình kích hoạt để đảm bảo rằng các cột mới này luôn được cập nhật khi bảng chính của tôi được cập nhật.

Để thực hiện một truy vấn k-khoảng cách sử dụng các vị sau đây:

(COLUMN1 = s [0]) + (column2 = s [1]) + (cột3 = s [2]) + (Column4 = s [3]) + ...> = m

trong đó s là chuỗi tìm kiếm của bạn và m là số ký tự khớp được yêu cầu (hoặc m = 9 - d trong trường hợp của tôi trong đó d là khoảng cách tối đa tôi muốn trả về).

Sau khi thử nghiệm, tôi nhận thấy rằng truy vấn trên 1 triệu hàng trung bình mất 4,6 giây đã trả về các id phù hợp trong chưa đầy một giây. Truy vấn thứ hai để trả về dữ liệu cho các hàng phù hợp trong bảng chính của tôi tương tự đã mất một giây. (Kết hợp hai truy vấn này dưới dạng truy vấn con hoặc tham gia dẫn đến thời gian thực thi dài hơn đáng kể và tôi không chắc chắn lý do.)

Mặc dù đây không phải là Damerau-Levenshtein (không thay thế) nó đủ cho mục đích của tôi.

Mặc dù giải pháp này có thể không mở rộng tốt cho không gian tìm kiếm lớn hơn (chiều dài) mà nó hoạt động tốt cho trường hợp hạn chế này.

Answer 7

Có một thực mysql UDF chức năng Levenshtein cách

https://github.com/jmcejuela/Levenshtein-MySQL-UDF

Nó được thực hiện trong C và có hiệu suất tốt hơn so với "truy vấn khoảng cách MySQL Levenshtein" được đề cập bởi schnaader

Answer 8

Nếu bạn chỉ muốn biết nếu khoảng cách levenshtein tối đa là 1, bạn có thể sử dụng hàm MySQL sau đây.

CREATE FUNCTION `lv_leq_1` (
`s1` VARCHAR(255) , 
`s2` VARCHAR(255) 
) RETURNS TINYINT(1) DETERMINISTIC 
BEGIN 
    DECLARE s1_len, s2_len, i INT; 
    SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), i = 1; 
    IF s1 = s2 THEN 
     RETURN TRUE; 
    ELSEIF ABS(s1_len - s2_len) > 1 THEN 
     RETURN FALSE; 
    ELSE 
     WHILE SUBSTRING(s1,s1_len - i,1) = SUBSTRING(s2,s2_len - i,1) DO 
      SET i = i + 1; 
     END WHILE; 
     RETURN SUBSTRING(s1,1,s1_len-i) = SUBSTRING(s2,1,s2_len-i) OR SUBSTRING(s1,1,s1_len-i) = SUBSTRING(s2,1,s2_len-i+1) OR SUBSTRING(s1,1,s1_len-i+1) = SUBSTRING(s2,1,s2_len-i); 
    END IF; 
END 

Điều này về cơ bản là một bước duy nhất trong mô tả đệ quy về khoảng cách levenshtein. Hàm trả về 1, nếu khoảng cách tối đa là 1, nếu không thì nó trả về 0.

Vì chức năng này không tính toán hoàn toàn khoảng cách levenshtein, nó sẽ nhanh hơn nhiều.

Bạn cũng có thể sửa đổi chức năng này sao cho nó trả về true nếu khoảng cách levenshtein tối đa là 2 hoặc 3, bằng cách gọi nó tự đệ quy. Nếu MySQL không hỗ trợ các cuộc gọi đệ quy, bạn có thể sao chép các phiên bản được sửa đổi đôi chút của chức năng này hai lần và gọi chúng thay thế. Nhưng bạn không nên sử dụng hàm đệ quy để tính toán khoảng cách levenshtein chính xác.

Answer 9

Chức năng được cung cấp cho levenshtein < = 1 ở trên không đúng - nó cho kết quả không chính xác ví dụ: "giường" và "giá thầu".

Tôi đã sửa đổi "truy vấn khoảng cách Levenshtein MySQL" đã nêu ở trên, trong câu trả lời đầu tiên, để chấp nhận "giới hạn" sẽ tăng tốc độ một chút. Về cơ bản, nếu bạn chỉ quan tâm đến Levenshtein < = 1, đặt giới hạn thành "2" và hàm sẽ trả về khoảng cách levenshtein chính xác nếu nó là 0 hoặc 1; hoặc 2 nếu khoảng cách levenshtein chính xác là 2 hoặc cao hơn.

Mod này giúp từ 15% đến 50% nhanh hơn - từ tìm kiếm càng dài, lợi thế càng lớn (vì thuật toán có thể bảo lãnh trước đó). Ví dụ: tìm kiếm 200.000 từ để tìm tất cả các kết quả phù hợp trong khoảng cách 1 của từ "cười khúc khích", bản gốc mất 3 phút 47 giây trên máy tính xách tay của tôi, so với 1:39 cho phiên bản "giới hạn". Tất nhiên, đây là cả hai quá chậm cho bất kỳ sử dụng thời gian thực.

Code:

DELIMITER $$ 
CREATE FUNCTION levenshtein_limit_n(s1 VARCHAR(255), s2 VARCHAR(255), n INT) 
    RETURNS INT 
    DETERMINISTIC 
    BEGIN 
    DECLARE s1_len, s2_len, i, j, c, c_temp, cost, c_min INT; 
    DECLARE s1_char CHAR; 
    -- max strlen=255 
    DECLARE cv0, cv1 VARBINARY(256); 
    SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0, c_min = 0; 
    IF s1 = s2 THEN 
     RETURN 0; 
    ELSEIF s1_len = 0 THEN 
     RETURN s2_len; 
    ELSEIF s2_len = 0 THEN 
     RETURN s1_len; 
    ELSE 
     WHILE j <= s2_len DO 
     SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1; 
     END WHILE; 
     WHILE i <= s1_len and c_min < n DO -- if actual levenshtein dist >= limit, don't bother computing it 
     SET s1_char = SUBSTRING(s1, i, 1), c = i, c_min = i, cv0 = UNHEX(HEX(i)), j = 1; 
     WHILE j <= s2_len DO 
      SET c = c + 1; 
      IF s1_char = SUBSTRING(s2, j, 1) THEN 
      SET cost = 0; ELSE SET cost = 1; 
      END IF; 
      SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost; 
      IF c > c_temp THEN SET c = c_temp; END IF; 
      SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1; 
      IF c > c_temp THEN 
       SET c = c_temp; 
      END IF; 
      SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1; 
      IF c < c_min THEN 
       SET c_min = c; 
      END IF; 
     END WHILE; 
     SET cv1 = cv0, i = i + 1; 
     END WHILE; 
    END IF; 
    IF i <= s1_len THEN -- we didn't finish, limit exceeded  
     SET c = c_min; -- actual distance is >= c_min (i.e., the smallest value in the last computed row of the matrix) 
    END IF; 
    RETURN c; 
    END$$ 

Answer 10

Dựa trên Chella's answer và Ryan Ginstrom của article, một tìm kiếm mờ có thể được thực hiện như vậy:

DELIMITER $$ 
CREATE FUNCTION fuzzy_substring(s1 VARCHAR(255), s2 VARCHAR(255)) 
    RETURNS INT 
    DETERMINISTIC 
BEGIN 
    DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT; 
    DECLARE s1_char CHAR; 
    -- max strlen=255 
    DECLARE cv0, cv1 VARBINARY(256); 
    SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0; 
    IF s1 = s2 THEN 
     RETURN 0; 
    ELSEIF s1_len = 0 THEN 
     RETURN s2_len; 
    ELSEIF s2_len = 0 THEN 
     RETURN s1_len; 
    ELSE 
     WHILE j <= s2_len DO 
      SET cv1 = CONCAT(cv1, UNHEX(HEX(0))), j = j + 1; 
     END WHILE; 
     WHILE i <= s1_len DO 
      SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1; 
      WHILE j <= s2_len DO 
       SET c = c + 1; 
       IF s1_char = SUBSTRING(s2, j, 1) THEN 
        SET cost = 0; ELSE SET cost = 1; 
       END IF; 
       SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost; 
       IF c > c_temp THEN SET c = c_temp; END IF; 
        SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1; 
       IF c > c_temp THEN 
        SET c = c_temp; 
       END IF; 
       SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1; 
      END WHILE; 
      SET cv1 = cv0, i = i + 1; 
     END WHILE; 
    END IF; 
    SET j = 1; 
    WHILE j <= s2_len DO 
     SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10); 
     IF c > c_temp THEN 
      SET c = c_temp; 
     END IF; 
     SET j = j + 1; 
    END WHILE; 
    RETURN c; 
END$$ 
DELIMITER ;