[Dictionary] Part 1: Tính Toán Khoảng Cách Levenshtein Nhanh Và Dễ ...

Bài này tôi dựa trên bài viết gốc tại đây: http://stevehanov.ca/blog/index.php?id=114 Tôi sẽ tiến hành viết 1 số bài về vấn đề từ điển dựa trên các bài trên blog của Steve. Đây là vấn đề xử lý cho từ điển và kiểm lỗi chính tả.

Khái niệm cơ bản Levenshtein distance: Khoảng cách Levenshtein. Trie: Cây tiền tố

Nếu bạn có một website riêng và có một hàm tìm kiếm, bạn sẽ dễ dàng nhận ra phần lớn các vấn đề phiền toái gây ra là các dữ liệu nhập vào để tìm kiếm. Có quá nhiều những tìm kiếm với những từ không tồn tại, cái này có thể là lỗi người dùng, tuy nhiên người dùng nào mà lại không mong một chút kỳ diệu gì đó cho quá trình tìm kiếm, nhưng việc nhận ra người dùng có phải tìm từ này không khi gõ sai chính tả chẳng hạn. Công việc này tính ra cũng không có gì là xa lạ, một số từ điển và thậm chí một số search engine (Như Bing hay Google) cũng đã gợi ý các từ khi người dùng gõ sai chính tả. Việc làm này kỳ diệu này thường được thực hiện bằng một công cụ gọi gọi là Khoảng cách Levenshtein. Trong tài liệu này, tôi sẽ so sánh hai cách để tìm kiếm các từ thích hợp trong một từ điển lớn. Tôi sẽ miêu tả tôi đã sử dụng nó như thế nào ở trang rhymebrain.com, nó có thể không chính xác, như với một tìm kiếm trên 2.6 triệu từ để phát âm với mỗi request, không sử dụng cache, trên cái máy chủ "siêu mạnh" của tôi. Phần này lưu ý là Steve đã vui tính gọi con Acer Aspire One của mình là cái máy chủ "siêu mạnh":

Phần cứng: 1.6 GHz Atom processor (with hyperthreading) 512 MB memory 8 GB SSD Wifi, etherne VGA ports 3 USB ports and 2 SD card slots (?!) Phần mềm: OS: Ubuntu 9.04 Webserver: Apache2 đã tối giản hóa

Giải thuật:

Hàm tính khoảng cách Levenshtein nhận 2 tham số là 2 từ và trả về khoảng cách giữa chúng. Nó là một thuật toán với độ phức tạo O(N*M) với N là độ dài từ đầu, và M là độ dài chữ còn lại. Nếu cụ thể muốn biết nó làm việc như thế nào bạn có thể xem trên Wikipedia.

Tuy nhiên việc so sánh 2 từ một lần tỏ ra không hiệu quả. Thường bạn muốn tìm những từ tương tự với nó trong từ điển, thậm chí có thể là hàng ngàn từ. Sau đây là đoạn code Python làm việc trên, sử dụng không phức tạo tuy nhiên cách này chậm. File từ điển có đường dẫn tại /usr/share/dict/words. Tham số đầu tiên là từ viết sai chính tả, tham số thứ 2 là khoảng cách tối đa. Kết quả in ra sẽ là các từ cùng khoảng cách của chúng, đoạn code làm việc tốt dù hơi tốn thời gian. Ví dụ kết quả:

smhanov@ubuntu1004:~$ ./method1.py goober 1 ('goober', 0) ('goobers', 1) ('gooier', 1) Search took 4.5575 s

Đoạn code:

#!/usr/bin/python #By Steve Hanov, 2011. Released to the public domain import time import sys DICTIONARY = "/usr/share/dict/words"; TARGET = sys.argv[1] MAX_COST = int(sys.argv[2]) # read dictionary file words = open(DICTIONARY, "rt").read().split(); # for brevity, we omit transposing two characters. Only inserts, # removals, and substitutions are considered here. def levenshtein( word1, word2 ): columns = len(word1) + 1 rows = len(word2) + 1 # build first row currentRow = [0] for column in xrange( 1, columns ): currentRow.append( currentRow[column - 1] + 1 ) for row in xrange( 1, rows ): previousRow = currentRow currentRow = [ previousRow[0] + 1 ] for column in xrange( 1, columns ): insertCost = currentRow[column - 1] + 1 deleteCost = previousRow[column] + 1 if word1[column - 1] != word2[row - 1]: replaceCost = previousRow[ column - 1 ] + 1 else: replaceCost = previousRow[ column - 1 ] currentRow.append( min( insertCost, deleteCost, replaceCost ) ) return currentRow[-1] def search( word, maxCost ): results = [] for word in words: cost = levenshtein( TARGET, word ) if cost <= maxCost: results.append( (word, cost) ) return results start = time.time() results = search( TARGET, MAX_COST ) end = time.time() for result in results: print result print "Search took %g s" % (end - start)

Với mỗi so sánh, chúng sẽ xây dựng một bảng kích thước NxM.

Cải tiến

Chúng ta hãy xem kết quả chạy với cụm (cat, kate).

k	a	t	e
0	1	2	3	4
c	1	1	2	3	4
a	2	2	1	2	3
t	3	3	2	1	2

Đoạn code trên sẽ chạy tốt cụm từ (cat, kate). Tuy nhiên, nếu từ cat tiếp tục mở rộng phần sau của nó ra như trở thành từ cats thì sao?

k	a	t	e
0	1	2	3	4
c	1	1	2	3	4
a	2	2	1	2	3
t	3	3	2	1	2
s	4	4	3	2	2

Việc trên chỉ làm thay đổi hàng cuối trong bảng. Chúng ta có thể tránh việc xử lý một lượng tính toán lớn bằng cách không lặp lại các tính toán trùng lặp như bên trên. Cấu trúc cây tiền tố (Trie) là một sự lựa chọn hoàn hảo để giải quyết vấn đề này. Cây tiền tố là một cây rất lớn, tại đó mỗi nút thể hiện một phần hoặc một từ trọn vẹn. Ở đây nó là một thể hiện của các từ sau: cat, cats, catacomb, and catacombs. Các nút thể hiện một từ rõ ràng tại các nút màu đen.

Với một cây tiền tối, tất cảc các thành phần cùng tiền tố sẽ được thu gọn vào cùng một nhánh của cây, chúng ta có thể sắp xếp chúng một cách tối ưu rồi xử lý chúng chỉ trong 1 lần duy nhất. Đây là code Python làm việc trên:

#!/usr/bin/python #By Steve Hanov, 2011. Released to the public domain import time import sys DICTIONARY = "/usr/share/dict/words"; TARGET = sys.argv[1] MAX_COST = int(sys.argv[2]) # Keep some interesting statistics NodeCount = 0 WordCount = 0 # The Trie data structure keeps a set of words, organized with one node for # each letter. Each node has a branch for each letter that may follow it in the # set of words. class TrieNode: def __init__(self): self.word = None self.children = {} global NodeCount NodeCount += 1 def insert( self, word ): node = self for letter in word: if letter not in node.children: node.children[letter] = TrieNode() node = node.children[letter] node.word = word # read dictionary file into a trie trie = TrieNode() for word in open(DICTIONARY, "rt").read().split(): WordCount += 1 trie.insert( word ) print "Read %d words into %d nodes" % (WordCount, NodeCount) # The search function returns a list of all words that are less than the given # maximum distance from the target word def search( word, maxCost ): # build first row currentRow = range( len(word) + 1 ) results = [] # recursively search each branch of the trie for letter in trie.children: searchRecursive( trie.children[letter], letter, word, currentRow, results, maxCost ) return results # This recursive helper is used by the search function above. It assumes that # the previousRow has been filled in already. def searchRecursive( node, letter, word, previousRow, results, maxCost ): columns = len( word ) + 1 currentRow = [ previousRow[0] + 1 ] # Build one row for the letter, with a column for each letter in the target # word, plus one for the empty string at column 0 for column in xrange( 1, columns ): insertCost = currentRow[column - 1] + 1 deleteCost = previousRow[column] + 1 if word[column - 1] != letter: replaceCost = previousRow[ column - 1 ] + 1 else: replaceCost = previousRow[ column - 1 ] currentRow.append( min( insertCost, deleteCost, replaceCost ) ) # if the last entry in the row indicates the optimal cost is less than the # maximum cost, and there is a word in this trie node, then add it. if currentRow[-1] <= maxCost and node.word != None: results.append( (node.word, currentRow[-1] ) ) # if any entries in the row are less than the maximum cost, then # recursively search each branch of the trie if min( currentRow ) <= maxCost: for letter in node.children: searchRecursive( node.children[letter], letter, word, currentRow, results, maxCost ) start = time.time() results = search( TARGET, MAX_COST ) end = time.time() for result in results: print result print "Search took %g s" % (end - start)

Đây là kết quả:

smhanov@ubuntu1004:~$ ./method1.py goober 1 Read 98568 words into 225893 nodes ('goober', 0) ('goobers', 1) ('gooier', 1) Search took 0.0141618 s

Giải thuật này chạy nhanh hơn 300 lần so với giải thuật đề cập trước đó. Tại sao vậy? Bởi vì chúng ta đã tạo mỗi hàng trong bảng cho từng nút trong cây tiền tố. Giới hạn tốt kém của giải thuật là O(<từ dài nhất> * <số nút trong cây tiền tố>). Hầu hết các từ điển,  tốn kém nhỏ hơn O(<số từ> * <từ dài nhất>^2).

Tiết kiệm bộ nhớ ?

Xây dựng một cây tiền tố sẽ tốt rất nhiều bộ nhớ. Trong Phần2, tôi sẽ nói rõ làm thể nào để xây dựng một MA-FSA (hay DAWG) để chứa những thông tin tương tự tuy nhiên nhỏ gọn hơn.

RhymeBrain

Trong tháng 12, tôi nhận thấy Google đã phát hành N-grams data, một danh sách các từ được scan từ các cuốn sách của Google Book. Tôi đã thêm tất cả vào RhymeBrain, kích thước từ điển của tôi tăng từ 260,000 lên 2.6 triệu từ, và vấn đề tối ưu hiệu xuất xuất hiện.

Tôi đã lưu tất cả các từ trong một cây tiền tố, lập chỉ mục cách phát âm. Tuy vậy, để tìm kiếm trên nó, tong lần khởi tạo tôi sử sử dụng một cách nhanh và đê tiện đó quét các từ có thể phát âm. Sau đó tôi đã lấy một danh sách lớn và chạy nó một lượt sử dụng hàm Levenshtein để tính  RhymeRankTM . Người dùng có thể chỉ thấy 50 mục từ của danh sách.

Sau khi suy nghĩ sâu hơn, tôi nhận thấy rằng hàm Levenshtein có thể còn mở rộng hiểu quả hơn, như tôi nói ở bên trên. Dĩ nhiên, tôi có thể đã có thể nhận ra sớm hơn nếu tôi đã đọc nhiều bài viết học thuật hơn về vấn đề này, chúng đã mô tả chính xác phương pháp này.

Với một giải thuật mới, truy vấn tốn thời gian từ 19 đến 50ms với cả những từ dài, nhưng phần tốt đẹp nhất của nó mà tôi không cần quan tâm tới 2 việc nhanh và đầy đủ, đó là việc hiệu xuất là đồng nhất cho mỗi truy vấn với 2.6 triệu từ trên cái datacenter 1GHz Acer Aspire One của tôi.

Chia sẻ:

• Facebook
• Twitter
• In
• Email

Thích Đang tải...

Có liên quan