Thuật toán khoảng cách Levenshtein tốt hơn O (n * m)?

Question

Tôi đã tìm kiếm thuật toán khoảng cách levenshtein tiên tiến và the best I have found so far là O (n * m) trong đó n và m là độ dài của hai chuỗi. Lý do tại sao các thuật toán là ở quy mô này là bởi vì không gian, không thời gian, với việc tạo ra một ma trận của hai chuỗi như thế này:

Có một thuật toán Levenshtein công khai có sẵn cái nào tốt hơn O (n * m)? Tôi không thích đọc các bài báo khoa học máy tính tiên tiến & nghiên cứu, nhưng không thể tìm thấy bất cứ điều gì. Tôi đã tìm thấy một công ty, Exorbyte, được cho là đã xây dựng một thuật toán Levenshtein siêu tiên tiến và siêu nhanh nhưng tất nhiên đó là một bí mật thương mại. Tôi đang xây dựng một ứng dụng iPhone mà tôi muốn sử dụng tính toán khoảng cách Levenshtein. There is an objective-c implementation available, nhưng với số lượng bộ nhớ hạn chế trên iPod và iPhone, tôi muốn tìm một thuật toán tốt hơn nếu có thể.

Answer 1

Bạn có muốn giảm độ phức tạp về thời gian hoặc độ phức tạp của không gian không? Độ phức tạp trung bình thời gian có thể được giảm O (n + d^2), trong đó n là độ dài của chuỗi dài hơn và d là khoảng cách chỉnh sửa. Nếu bạn chỉ quan tâm đến khoảng cách chỉnh sửa và không quan tâm đến việc xây dựng lại chuỗi chỉnh sửa, bạn chỉ cần giữ hai hàng cuối cùng của ma trận trong bộ nhớ, do đó sẽ là thứ tự (n).

Nếu bạn có thể đủ khả năng để ước tính, có các xấp xỉ poly-logarit.

Đối với thuật toán O (n + d^2), hãy tìm tối ưu hóa hoặc cải tiến của Ukkonen Enhanced Ukkonen. Phép tính gần đúng nhất mà tôi biết là số này theo Andoni, Krauthgamer, Onak

Answer 2

Look in Wiki - họ có một số ý tưởng để cải thiện thuật toán này phức tạp không gian tốt hơn:

Wiki-Link: Levenshtein distance

Trích dẫn:

Chúng ta có thể thích nghi với các thuật toán để sử dụng không gian ít hơn, O (m) thay vì O (mn), vì nó chỉ yêu cầu hàng trước và hàng hiện tại được lưu trữ cùng một lúc.

Answer 3

Nếu bạn chỉ muốn hàm ngưỡng - ví dụ: để kiểm tra xem khoảng cách có dưới ngưỡng nhất định hay không - bạn có thể giảm thời gian và không gian phức tạp bằng cách chỉ tính n các giá trị ở hai bên của đường chéo chính trong mảng. Bạn cũng có thể sử dụng Levenshtein Automata để đánh giá nhiều từ đối với một từ cơ sở duy nhất trong thời gian O (n) - và việc xây dựng các automatons cũng có thể được thực hiện trong thời gian O (m).

Answer 4

Tôi tìm thấy một tối ưu hóa mà tuyên bố là O (max (m, n)):

http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C

(C thi thứ hai)