Soundex

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Soundex là một thuật toán ngữ âm để liệt kê các từ theo âm sắc, theo cách phát âm của tiếng Anh. Mục đích là mã hóa những từ có cùng cách phát âm qua những đặc trưng giống nhau, từ đó người ta có thể tìm được một từ nào đó dù có sai sót nhỏ trong chính tả từ đó. Thuật toán Soundex là thuật toán được sử dụng rộng rãi nhất trong các thuật toán ngữ âm. Rất nhiều thuật toán ngữ âm hiện có nền tảng từ sự cải tiến của thuật toán Soundex.

Lịch sử[sửa | sửa mã nguồn]

Soundex được phát triển bơi Robert Russell và Margaret Odell, được cấp bằng sáng chế vào các năm 1918[1] và 1922 [2]. Một biến thể của Soundex là thuật toán American Soundex được sử dụng trong những năm 1930 để xem xét lại quá trình điều tra dân số Mỹ những năm từ 1890 cho đến 1920. Mã Soundex trở nên phổ biến vào những năm 1960, khi là chủ đề của nhiều bài báo trên tạp chí và các phương tiện truyền thông của ACM, và đặc biệt là sau khi được Donald Knuth miêu tả chi tiết trong cuốn sách nổi tiếng của ông - The Art of Computer Programming.

Quy tắc cơ bản[sửa | sửa mã nguồn]

Mã Soundex trả về một xâu bao gồm có một chữ cái và 3 trong số theo sau: chữ cái là chữ cái đầu tiên của từ đó, và các số mã hóa cho các phụ âm còn lại. Các phụ âm có âm sắc giống nhau được mã bởi các trọng số giống nhau, ví dụ, âm lưỡi B, F, P, và V được mã hóa là 1. Các nguyên âm có thể ảnh hưởng đến việc mã hóa, nhưng không bao giờ được mã hóa trực tiếp trừ khi chúng xuất hiện ngay ở đầu của từ.

Thuật toán chi tiết như sau:

  1. Lưu chữ cái đầu tiên trong xâu.
  2. Loại bỏ mọi chữ cái sau đây, trừ khi nó là chữ cái đầu tiên: a, e, h, i, o, u, w, y
  3. Gán các trọng số cho các chữ cái còn lại (sau chữ cái đầu tiên) như sau:
    • b, f, p, v = 1
    • c, g, j, k, q, s, x, z = 2
    • d, t = 3
    • l = 4
    • m, n = 5
    • r = 6
  4. Nếu 2 hay nhiều chữ cái có trọng số giống nhau ở sát nhau trong từ ban đầu (trước bước 1), hay cách nhau chỉ bởi chữ h hay chữ w (chỉ có trong tiếng Mỹ), thì bỏ qua tất cả.
  5. Trả lại 4 ký tự đầu tiên, thêm 0 vào bên phải nếu ít hơn 4 ký tự được trả về.

Sử dụng thuật toán này, cả "Robert" và "Rupert" đều trả về chuỗi "R163" trong khi từ "Rubin" sẽ trả về "R150".

Thuật toán áp dụng cho tiếng Mỹ[sửa | sửa mã nguồn]

Vẫn tuân theo thuật toán cơ bản, nhưng có thêm các yêu cầu sau:

  1. Không quan tâm đến các phụ âm W, H, Y và các nguyên âm A, E, I, O, U.
  2. Khi có 2 hay nhiều chữ cái có cùng trọng số ở cạnh nhau, thì chỉ mã hóa một chữ cái. Ví dụ:
    • Sheppard S-163
    • Sacks S-200
  3. Một chữ cái đi ngay sau chữ cái đầu tiên và có cùng trọng số với chữ cái đầu tiên thì bỏ qua chữ cái này (không mã hóa). Ví dụ:
    • Schebowitz S-132
    • Scklar S-460
  4. 2 hay nhiều chữ cái chỉ cách nhau bởi chữ H hay W thì chỉ mã hóa một chữ cái. Ví dụ:
    • Sokwzy S-200
    • Schkolink S-452
  5. Khi một chữ cái lập lại nhiều lần và được ngăn cách bởi một hay nhiều nguyên âm A, E, I, O, U hoặc Y, ta vẫn mã hóa tất cả các chữ cái đó. Ví dụ:
    • Staten S-335
    • Simone S-550
  6. Với những từ không chứa bất kỳ chữ cái nào có 1 trong 6 trọng số trên - tức là sau chữ cái đầu chỉ có các chữ cái không có trọng số, ta gán toàn bộ số trọng số sau là 0. Ví dụ:
    • Shea S-000
    • Lee L-000

Liên kết ngoài[sửa | sửa mã nguồn]