Sách về thuật toán chuỗi

Question

Đã có rất nhiều bài viết trên các thuật toán chuỗi:

• Algorithm to find articles with similar text,
• Similar String algorithm,
• Efficient string matching algorithm

Tuy nhiên, không có tài liệu nói chung được nhắc đến.

Ai đó có thể giới thiệu một (các) cuốn sách sẽ khám phá kỹ lưỡng các thuật toán chuỗi khác nhau không? Chủ đề được quan tâm đặc biệt là đối sánh chuỗi gần đúng [những thứ như các biến thể chuỗi tìm kiếm được cung cấp bởi google được cung cấp :)].

Cảm ơn rất nhiều lời khuyên.

Answer 1

Tôi ngạc nhiên khi không ai đề cập đến cuốn sách tuyệt vời của Dan Gusfield Algorithms on Strings, Trees and Sequences bao gồm các thuật toán chuỗi chi tiết hơn bất kỳ ai có thể sẽ cần. Nó phục vụ tôi rất tốt cho một dự án về trình tự protein mà tôi đã làm việc trên một vài năm trước đây. Sau khi đọc cuốn sách này bạn sẽ học:

• Chuỗi Naive Matching
• thuật toán Preprocessor Dựa (Boyer Moore, Knuth-Morris-Pratt)
• Regex phù hợp với các thuật toán
• Karp-Rabin và phương pháp tương tự
• Phương pháp cây hậu tố (phương pháp của Ukkonen, v.v.)
• Căn chỉnh chuỗi (khoảng cách Levenshtein và độ tương tự chuỗi và liên kết nhiều chuỗi)
• Các ứng dụng để sắp xếp trình tự DNA, dự đoán gen và các khu vực khác.

Answer 2

CLR có một số thuật toán xử lý chuỗi nhưng không cụ thể với chúng.

Bao gồm:

• Knuth-Morris-Pratt
• Rabin-Karp
• khớp bởi automata hữu hạn
• chỉnh sửa khoảng cách

Answer 3

TRE là một thư viện mã nguồn mở mà thực hiện phù hợp tương đối. About page có một số gợi ý thú vị về cách nó hoạt động, mặc dù tôi không chắc nó cung cấp loại phân tích chuyên sâu mà bạn đang tìm kiếm. Mã nguồn có lẽ là sự khai sáng nhiều hơn từ quan điểm đó.

Answer 4

Đây không phải là một đề nghị cuốn sách, nhưng thư viện này và trang web là một thư viện cung cấp rất nhiều hiện thực giải thuật chuỗi kết hợp hiệu quả:

http://www.dcs.shef.ac.uk/~sam/simmetrics.html

Nó cũng cung cấp các liên kết để tiếp tục học tập cho mỗi người và trong đó mỗi được áp dụng tốt nhất.

Answer 5

Jewels of Stringology