Làm cách nào để tìm kiếm chuỗi mờ mà không có cơ sở dữ liệu nặng?

Question

Tôi có một bản đồ số catalô vào tên sản phẩm:

35 cozy comforter 
35 warm blanket 
67 pillow 

và cần một tìm kiếm sẽ tìm thấy sai chính tả, tên hỗn hợp như "cmfrter ấm".

Chúng tôi có mã bằng cách sử dụng khoảng cách chỉnh sửa (difflib), nhưng nó có thể sẽ không chia tỷ lệ thành tên 18000.

Tôi đã đạt được một cái gì đó tương tự với Lucene, nhưng như PyLucene chỉ kết thúc tốt đẹp Java sẽ phức tạp triển khai cho người dùng cuối.

SQLite thường không có đầy đủ các văn bản hoặc ghi bàn biên soạn trong.

Các Xapian bindings giống như C++ và có một số đường cong học tập.

Whoosh chưa được ghi chép đầy đủ nhưng bao gồm trình kiểm tra chính tả có thể sử dụng được.

Còn gì nữa?

Answer 1

Nucular có tìm kiếm văn bản đầy đủ, nhưng nó không hỗ trợ các trận đấu sai chính tả out-of-the-box. Bạn có thể thử thêm một trường bổ sung vào mỗi mục nhập để lập chỉ mục các cụm từ SOUNDEX của các cụm từ và sau đó tìm kiếm bằng cách sử dụng bản dịch âm thanh của đầu vào của người dùng. Tôi thật sự không biết điều này sẽ làm việc tốt như thế nào ...

Hãy xem advas http://advas.sourceforge.net/news.php trong đó có một bản demo đẹp so sánh khác nhau phương pháp Soundex tương tự:

advas/examples Aaron$ python phonetic_algorithms.py 
        soundex  metaphone   nyiis  caverphone 
==================================================================================================== 
schmidt :    S253   sxmtt   sssnad  SKMT111111 
    schmid :    S253   sxmt   sssnad  SKMT111111 
schmitt :    S253   sxmt   sssnatt  SKMT111111 
    smith :    S530   sm0h   snatt  SMT1111111 
    smythe :    S530   smy0h   snatt  SMT1111111 
schmied :    S253   sxmt   sssnaad  SKMT111111 
    mayer :    M600    myr   naaar  MA11111111 
    meier :    M600    mr   naaar  MA11111111 
.... 

Tôi không biết nếu bất kỳ ngôn ngữ nào trong số đó đều tốt cho ngôn ngữ không được đặt tên của bạn ...

Answer 2

Bạn sẽ nhận được quá nhiều xác thực sai với việc triển khai SOUNDEX. Chỉ có 26.000 (tối đa) mã SOUNDEX có thể.

Mặc dù thuật toán Metaphone được thiết kế cho họ tiếng Anh, nhưng nó hoạt động khá tốt với lỗi chính tả; Tôi đã sử dụng nó một lần trong một định vị chi nhánh và nó đã khá thành công.

Thêm trường bằng bản dịch Metaphone và khớp với nó nếu không tìm thấy kết quả khớp chính xác. Bạn sẽ vẫn nhận được các kết quả sai, nhưng ít hơn với các thuật toán khác.

Answer 3

Cách thông thường để tính toán khoảng cách chỉnh sửa giữa hai chuỗi là một thuật toán khá tốn kém (nếu tôi nhớ chính xác thì độ phức tạp của nó là bậc hai). Có thể nếu bạn đã sử dụng một chỉ số tương tự chuỗi khác thì vấn đề của bạn sẽ biến mất.

Một trong những phương pháp yêu thích của tôi để đối sánh chuỗi mờ là trigrams matching. So sánh hai chuỗi bằng cách sử dụng phương pháp này có độ phức tạp thời gian tuyến tính, tốt hơn nhiều so với khoảng cách chỉnh sửa được đề cập. Bạn có thể tìm thấy triển khai Python của tôi trên Github. Ngoài ra còn có một PostgreSQL contrib module chính xác cho điều đó. Nó không quá khó để thích ứng với nó để làm việc với SQLite3.

Answer 4

Sybase SQL Anywhere có phiên bản web miễn phí/Phiên bản dành cho nhà phát triển và đi kèm với lập chỉ mục/tìm kiếm toàn văn và toán tử FUZZY (và một số ràng buộc triển khai).

Để trích dẫn từ tài liệu:

Specifying 'FUZZY "500 main street"' is equivalent to 
'500 OR mai OR ain OR str OR tre OR ree OR eet'. 

Một cách tiếp cận khác sẽ được sử dụng cho điểm trên các tìm kiếm toàn văn.

Answer 5

Rõ ràng là cách duy nhất để so sánh mờ nhanh chóng là để làm ít trong số họ;)

Thay vì viết khác tìm kiếm n-gram hoặc cải thiện một trong bất ngờ tới thăm bây giờ chúng tôi giữ một chỉ số văn bản, lấy tất cả các mục mà có ít nhất một từ (đúng chính tả) từ chung với truy vấn và sử dụng difflib để xếp hạng các từ đó. Hoạt động tốt trong trường hợp này.

Answer 6

sqlite3 hỗ trợ chức năng gọi lại trăn. Matthew regex regex (http://code.google.com/p/mrab-regex-hg/) bây giờ hỗ trợ phù hợp gần đúng.

Vì vậy, như thế này:

try: 
    import regex 
except ImportError: 
    sys.stderr.write("Can't import mrab-regex; see http://pypi.python.org/pypi/regex\n") 
    sys.exit(1) 

def _sqlite3_regex(expr, item): 
    return (not (not regex.search(expr, item))) 

def main(): 
    ... 
    database = sqlite3.connect(dbfile) 
    database.create_function("regexp", 2, _sqlite3_regex) 
    pattern = '(?:%s){e<=%d}' % (queriedname, distance) 
    print [x for x in database.cursor().execute(
     "SELECT * FROM products WHERE (productname regexp '%s')" % pattern)]