Khi bạn đang viết mã để tìm kiếm cơ sở dữ liệu, bạn không thể dựa vào tất cả các mục nhập dữ liệu được viết đúng chính tả. Doug Hellmann, nhà phát triển tại DreamHost và là tác giả của Thư viện tiêu chuẩn Python theo ví dụ, đánh giá các tùy chọn có sẵn để tìm kiếm cơ sở dữ liệu theo âm thanh của tên mục tiêu, thay vì dựa vào độ chính xác của mục nhập
Tìm kiếm tên của một người trong cơ sở dữ liệu là một thách thức độc đáo. Tùy thuộc vào nguồn và độ tuổi của dữ liệu, bạn có thể không tin rằng cách viết của tên đó là chính xác hoặc thậm chí tên giống nhau được đánh vần theo cùng một cách khi nó xuất hiện nhiều lần. Sự khác biệt giữa dữ liệu được lưu trữ và cụm từ tìm kiếm có thể được đưa ra do lựa chọn cá nhân hoặc sự khác biệt về văn hóa trong cách viết, từ đồng âm, lỗi phiên âm, mù chữ hoặc đơn giản là thiếu cách viết chuẩn trong một số khoảng thời gian. Những loại vấn đề này đặc biệt phổ biến trong việc sao chép các ghi chép lịch sử viết tay được sử dụng bởi các nhà sử học, nhà phả hệ và các nhà nghiên cứu khác.
Một cách phổ biến để giải quyết vấn đề tìm kiếm chuỗi là tìm kiếm các giá trị "gần giống" với mục tiêu tìm kiếm. Tuy nhiên, việc sử dụng thuật toán so khớp mờ truyền thống để tính toán mức độ gần nhau của hai chuỗi tùy ý là rất tốn kém và không phù hợp để tìm kiếm các tập dữ liệu lớn. Một giải pháp tốt hơn là tính toán trước các giá trị băm cho các mục nhập trong cơ sở dữ liệu và một số thuật toán băm đặc biệt đã được tạo cho mục đích này. Các thuật toán băm ngữ âm này cho phép bạn so sánh hai từ hoặc tên dựa trên cách phát âm của chúng, thay vì cách viết chính xác
Nỗ lực sớm. âm thanh
Một thuật toán như vậy là Soundex, được phát triển bởi Margaret K. Odell và Robert C. Russell vào đầu những năm 1900. Thuật toán Soundex xuất hiện thường xuyên trong ngữ cảnh phả hệ vì nó được liên kết với U. S. Điều tra dân số và được thiết kế đặc biệt để mã hóa tên. Giá trị băm Soundex được tính bằng cách sử dụng chữ cái đầu tiên của tên và chuyển đổi các phụ âm trong phần còn lại của tên thành chữ số bằng cách sử dụng bảng tra cứu đơn giản. Các nguyên âm và giá trị được mã hóa trùng lặp bị loại bỏ và kết quả được thêm vào—hoặc bị cắt bớt xuống—bốn ký tự
Thư viện Fuzzy bao gồm triển khai Soundex cho các chương trình Python
#!/usr/bin/env python
import fuzzy
names = [ 'Catherine', 'Katherine', 'Katarina',
'Johnathan', 'Jonathan', 'John',
'Teresa', 'Theresa',
'Smith', 'Smyth',
'Jessica',
'Joshua',
]
soundex = fuzzy.Soundex[4]
for n in names:
print '%-10s' % n, soundex[n]Đầu ra của show_soundex. py chứng minh rằng một số tên có âm thanh tương tự được mã hóa với cùng giá trị băm, nhưng kết quả không lý tưởng
$ python show_soundex.py Catherine C365 Katherine K365 Katarina K365 Johnathan J535 Jonathan J535 John J500 Teresa T620 Theresa T620 Smith S530 Smyth S530 Jessica J200 Joshua J200
Trong ví dụ này, các biến thể Theresa và Teresa đều tạo ra cùng một hàm băm Soundex, nhưng Catherine và Katherine bắt đầu bằng một chữ cái khác; . Hai tên cuối cùng, Jessica và Joshua, hoàn toàn không liên quan nhưng được cung cấp cùng một giá trị băm vì các chữ cái J, S và C đều ánh xạ tới chữ số 2 và thuật toán loại bỏ các tên trùng lặp. Những loại lỗi này minh họa cho một thiếu sót lớn của Soundex
ngoài tiếng anh. NYSIIS
Các thuật toán được phát triển sau Soundex sử dụng các lược đồ mã hóa khác nhau, được xây dựng trên Soundex bằng cách điều chỉnh bảng tra cứu hoặc bắt đầu lại từ đầu với các quy tắc của riêng chúng. Tất cả đều xử lý các âm vị khác nhau nhằm cố gắng cải thiện độ chính xác. Ví dụ, vào những năm 1970, thuật toán Hệ thống tình báo và nhận dạng bang New York [NYSIIS] đã được xuất bản bởi Robert L. taft. NYSIIS ban đầu được sử dụng bởi Bộ phận Dịch vụ Tư pháp Hình sự của Tiểu bang New York để giúp xác định những người trong cơ sở dữ liệu của họ. Nó tạo ra kết quả tốt hơn Soundex vì nó đặc biệt cẩn thận để xử lý các âm vị xuất hiện trong họ của người Châu Âu và Tây Ban Nha
#!/usr/bin/env python
import fuzzy
names = [ 'Catherine', 'Katherine', 'Katarina',
'Johnathan', 'Jonathan', 'John',
'Teresa', 'Theresa',
'Smith', 'Smyth',
'Jessica',
'Joshua',
]
for n in names:
print '%-10s' % n, fuzzy.nysiis[n]Đầu ra của show_nysiis. py tốt hơn kết quả từ Soundex với dữ liệu mẫu của chúng tôi
$ python show_nysiis.py Catherine CATARAN Katherine CATARAN Katarina CATARAN Johnathan JANATAN Jonathan JANATAN John JAN Teresa TARAS Theresa TARAS Smith SNATH Smyth SNATH Jessica JASAC Joshua JAS
Trong trường hợp này, Catherine, Kinda và Katarina đều ánh xạ tới cùng một giá trị băm. Kết hợp không chính xác của Jessica và Joshua cũng bị loại bỏ vì nhiều chữ cái trong tên được sử dụng trong giá trị băm NYSIIS
Một cách tiếp cận mới. siêu âm
Metaphone, được xuất bản năm 1990 bởi Lawrence Philips, là một thuật toán khác cải tiến trên các hệ thống trước đó như Soundex và NYSIIS. Thuật toán Metaphone phức tạp hơn nhiều so với các thuật toán khác vì nó bao gồm các quy tắc đặc biệt để xử lý sự không nhất quán về chính tả và để xem xét sự kết hợp của các phụ âm ngoài một số nguyên âm. Một phiên bản cập nhật của thuật toán, được gọi là Double Metaphone, thậm chí còn tiến xa hơn bằng cách thêm các quy tắc để xử lý một số cách viết và cách phát âm từ các ngôn ngữ khác ngoài tiếng Anh
#!/usr/bin/env python
import fuzzy
names = [ 'Catherine', 'Katherine', 'Katarina',
'Johnathan', 'Jonathan', 'John',
'Teresa', 'Theresa',
'Smith', 'Smyth',
'Jessica',
'Joshua',
]
dmetaphone = fuzzy.DMetaphone[4]
for n in names:
print '%-10s' % n, dmetaphone[n]Ngoài việc có một bộ quy tắc mã hóa rộng hơn, Double Metaphone tạo hai giá trị băm thay thế cho mỗi từ đầu vào. Điều này mang lại cho người gọi khả năng trình bày kết quả tìm kiếm với hai cấp độ chính xác. Trong các kết quả từ chương trình mẫu, Catherine và Katherine có cùng giá trị băm chính. Giá trị băm phụ của chúng giống với giá trị băm chính của Katarina, tìm ra kết quả phù hợp mà Soundex không tìm thấy, nhưng mang lại ít trọng lượng hơn so với kết quả từ NYSIIS ngụ ý
$ python show_dmetaphone.py Catherine ['K0RN', 'KTRN'] Katherine ['K0RN', 'KTRN'] Katarina ['KTRN', None] Johnathan ['JN0N', 'ANTN'] Jonathan ['JN0N', 'ANTN'] John ['JN', 'AN'] Teresa ['TRS', None] Theresa ['0RS', 'TRS'] Smith ['SM0', 'XMT'] Smyth ['SM0', 'XMT'] Jessica ['JSK', 'ASK'] Joshua ['JX', 'AX']
Áp dụng tìm kiếm ngữ âm
Việc sử dụng tìm kiếm ngữ âm trong ứng dụng của bạn rất đơn giản nhưng có thể yêu cầu thêm tiện ích mở rộng vào máy chủ cơ sở dữ liệu hoặc gói thư viện của bên thứ ba với ứng dụng của bạn. MySQL, PostgreSQL, SQLite và Microsoft SQL Server đều hỗ trợ Soundex thông qua một hàm chuỗi có thể được gọi trực tiếp trong các truy vấn. PostgreSQL cũng bao gồm các hàm để tính toán giá trị băm bằng thuật toán Metaphone gốc và Double Metaphone
Các triển khai độc lập cho tất cả các thuật toán cũng có sẵn cho các ngôn ngữ lập trình chính như Python, PHP, Ruby, Perl, C/C++ và Java. Các thư viện này có thể được sử dụng với các cơ sở dữ liệu không hỗ trợ các hàm băm phiên âm được tích hợp sẵn, chẳng hạn như MongoDB. Ví dụ: tập lệnh này tải một loạt tên vào cơ sở dữ liệu, lưu từng giá trị băm dưới dạng giá trị được tính toán trước để giúp tìm kiếm dễ dàng hơn sau này
#!/usr/bin/env python
import argparse
import fuzzy
from pymongo import Connection
parser = argparse.ArgumentParser[description='Load names into the database']
parser.add_argument['name', nargs='+']
args = parser.parse_args[]
c = Connection[]
db = c.phonetic_search
dmetaphone = fuzzy.DMetaphone[]
soundex = fuzzy.Soundex[4]
for n in args.name:
# Compute the hashes. Save soundex
# and nysiis as lists to be consistent
# with dmetaphone return type.
values = {'_id':n,
'name':n,
'soundex':[soundex[n]],
'nysiis':[fuzzy.nysiis[n]],
'dmetaphone':dmetaphone[n],
}
print 'Loading %s: %s, %s, %s' % \
[n, values['soundex'][0], values['nysiis'][0],
values['dmetaphone']]
db.people.update[{'_id':n}, values,
True, # insert if not found
False,
]Chạy mongodb_load. py từ dòng lệnh để lưu tên để truy xuất sau
$ python mongodb_load.py Jonathan Johnathan Joshua Jessica Loading Jonathan: J535, JANATAN, ['JN0N', 'ANTN'] Loading Johnathan: J535, JANATAN, ['JN0N', 'ANTN'] Loading Joshua: J200, JAS, ['JX', 'AX'] Loading Jessica: J200, JASAC, ['JSK', 'ASK'] $ python mongodb_load.py Catherine Katherine Katarina Loading Catherine: C365, CATARAN, ['K0RN', 'KTRN'] Loading Katherine: K365, CATARAN, ['K0RN', 'KTRN'] Loading Katarina: K365, CATARAN, ['KTRN', None]
Chương trình tìm kiếm mongodb_search. py cho phép người dùng chọn một hàm băm và sau đó xây dựng truy vấn MongoDB để tìm tất cả các tên có giá trị băm khớp với tên đầu vào
________số 8Trong một số trường hợp mẫu này, các giá trị bổ sung trong tập hợp kết quả là mong muốn vì chúng khớp hợp lệ. Mặt khác, tìm kiếm Joshua trên Soundex lại trả về giá trị không liên quan Jessica. Mặc dù Soundex tạo ra kết quả kém khi so sánh với các thuật toán khác, nhưng nó vẫn được sử dụng trong nhiều trường hợp vì nó được tích hợp vào máy chủ cơ sở dữ liệu. Tính đơn giản của nó cũng có nghĩa là nó nhanh hơn NYSIIS hoặc Double Metaphone. Trong trường hợp kết quả đủ tốt, tốc độ của nó có thể là yếu tố quyết định trong việc lựa chọn nó
$ python mongodb_search.py soundex Katherine Katherine Katarina $ python mongodb_search.py nysiis Katherine Catherine Katherine Katarina $ python mongodb_search.py soundex Joshua Joshua Jessica $ python mongodb_search.py nysiis Joshua Joshua
Suy nghĩ cuối cùng
Tôi hy vọng rằng bài viết này đã chứng minh sức mạnh mà các thuật toán băm ngữ âm có thể thêm vào các tính năng tìm kiếm trong ứng dụng của bạn và sự dễ dàng mà bạn có thể triển khai chúng. Việc chọn thuật toán phù hợp để sử dụng sẽ tùy thuộc vào bản chất của dữ liệu và loại tìm kiếm bạn đang thực hiện. Nếu thuật toán phù hợp không rõ ràng từ dữ liệu có sẵn, thì tốt nhất nên cung cấp tùy chọn để cho phép người dùng chọn thuật toán băm phù hợp. Cung cấp cho người dùng một sự lựa chọn sẽ mang lại sự linh hoạt nhất cho việc thử nghiệm và tinh chỉnh các tìm kiếm, mặc dù điều đó đòi hỏi bạn phải làm thêm một chút để thiết lập các chỉ mục. Nhiều nhà nghiên cứu, nhà sử học và nhà phả hệ đã quen thuộc với tên của các thuật toán, nếu không phải là cách triển khai của chúng, vì vậy việc trình bày chúng dưới dạng các tùy chọn không nên khiến những người dùng này sợ hãi