5
Tôi đang cố gắng viết mô-đun kiểm tra chính tả.Tìm kiếm các từ tương tự
Nó tải văn bản, tạo từ điển từ tệp 16 mb và sau đó kiểm tra xem từ tương ứng với từ trong từ điển (tương tự = khác nhau đến hai ký tự), nếu sau đó nó thay đổi thành dạng từ điển.
Ngay bây giờ tôi đang sử dụng một thuật toán Levenshtein Khỏang cách và chế biến một 50 từ thiết mất 3 phút ...
Tôi khá chắc chắn rằng phải có một giải pháp nhanh hơn. Profiler nói với tôi rằng ứng dụng của tôi dành hơn 80% thời gian của nó trong hàm Levenshtein Distance.
Có giải pháp/thuật toán nào tốt hơn không?
Dưới đây là thực hiện các phiên bản của thuật toán tôi sử dụng:
def levenshteinDistance(s1, s2):
l_s1 = len(s1)
l_s2 = len(s2)
d = [[a for a in genM(x, l_s2 + 1)] for x in xrange(l_s1 + 1)]
for i in xrange(1, l_s1 + 1):
for j in xrange(1, l_s2 + 1):
d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + decide_of_equality(s1[i - 1],s2[j - 1]))
return d[l_s1][l_s2]
Âm thanh giống như "Tự động sửa" hơn kiểm tra chính tả, vì trình kiểm tra chính tả thường tạo tùy chọn và cho phép người dùng chọn trong số đó. Autocorrect là khá rõ ràng là không thể làm tốt, một thực tế hiện nay hầu như được thừa nhận, ngay cả trên quảng cáo truyền hình. :-) –
Nếu bạn giả định rằng chữ cái đầu tiên của từ luôn đúng, thì bạn chỉ có thể kiểm tra từ điển cho các từ bắt đầu bằng chữ cái đó. Nó sẽ giảm thời gian của bạn bởi nhiều hơn hoặc ít hơn một yếu tố hoặc 26 – Doboy
Tôi không biết nhiều về python, nhưng chức năng khoảng cách của bạn sử dụng giải pháp lập trình động tiêu chuẩn. Đây là phiên bản của tôi trong C++: http://codereview.stackexchange.com/questions/10130/edit-distance-between-two-strings có thể bạn có thể phát hiện một số khác biệt. –