Hạn chế và lựa chọn thay thế cho các ngôn ngữ khác ngoài tiếng Anh?

Question

Cấu trúc dữ liệu trie thường là cách tuyệt vời để lưu trữ chuỗi bằng tiếng Anh. Nó hoạt động bằng cách xây dựng một cây nơi mỗi cạnh được gắn nhãn bằng một chữ cái và đường dẫn đến một nút được đánh dấu trong cây sẽ giải thích một trong các từ trong cấu trúc dữ liệu.

Cấu trúc dữ liệu này hoạt động tốt bằng tiếng Anh vì có "chỉ" 26 chữ cái trong bảng chữ cái tiếng Anh (yếu tố phân nhánh "hợp lý"), các ký tự đó có giá trị ASCII liên tiếp (vì vậy con trỏ có thể được lưu trữ trong một mảng khóa) bởi chỉ số của các chữ cái được sử dụng bởi mỗi đứa trẻ), và có rất nhiều từ tiếng Anh với tiền tố phổ biến (vì vậy có rất nhiều dự phòng trong cấu trúc).

Tôi là một người nói tiếng Anh bản ngữ chỉ có kiến ​​thức hạn chế về các ngôn ngữ và bảng chữ cái khác, nhưng có vẻ như nhiều người trong số các thuộc tính này không chứa ngôn ngữ khác. Ví dụ, tôi biết rằng tiếng Pháp, tiếng Tây Ban Nha, tiếng Đức và tiếng Hungari thường sử dụng các ký tự có dấu trọng âm không được lưu trữ liên tục với các chữ cái còn lại trong không gian Unicode. Tiếng Do Thái và tiếng Ả Rập có các ký hiệu nguyên âm thường được biểu thị ở trên hoặc dưới mỗi chữ cái. Trung Quốc sử dụng một hệ thống nhật ký, và các nhân vật Hangul Hàn Quốc bao gồm ba nhân vật nhỏ hơn được nhóm lại với nhau.

Các nỗ lực vẫn hoạt động tốt cho dữ liệu được lưu trữ bằng các ngôn ngữ và bảng chữ cái này không? Những thay đổi nào, nếu có, là cần thiết để sử dụng các lần thử cho loại dữ liệu này? Có bất kỳ cấu trúc dữ liệu nào hoạt động tốt cho các chuỗi trong các ngôn ngữ và bảng chữ cái đó đặc biệt phù hợp với chúng nhưng sẽ không hữu ích hoặc hiệu quả bằng tiếng Anh không?

Answer 1

Là phụ lục cho câu trả lời của @ JimMischel, tôi muốn đưa ra vấn đề bằng các ngôn ngữ khác thường có nhiều cách tương đương để viết cùng một điều. Vietnamese (dựa trên kịch bản tiếng Latin/tiếng Anh) là một ví dụ đặc biệt tốt khi các chữ cái có hai điểm nhấn là phổ biến. Ví dụ, Ặ (U + 1EB6) có thể về mặt kỹ thuật cũng được viết bằng dãy số + dấu chấm, Ạ + breve, A + breve + dấu chấm, A + dấu chấm + dấu hai chấm.

Unicode normalization có thể giải quyết vấn đề này bằng cách chuyển đổi chuỗi thành thứ tự chuẩn chuẩn hóa. Có 4 biến thể khác nhau, NFC, NFKC, NFD và NFKD. Tôi sẽ không đi vào quá nhiều chi tiết ở đây, nhưng hai cái đầu tiên là "các dạng sáng tác" có xu hướng rút ngắn chuỗi ký tự, nhóm các ký tự cơ bản với dấu của nó, trong khi hai ký tự cuối cùng là "dạng bị phân tách", làm ngược lại.

Hangul là một trường hợp thú vị: Đây là bảng chữ cái, mặc dù tất cả các chữ cái của một âm tiết được viết cùng nhau trong một khối. Cả hai chữ cái riêng lẻ và các khối âm tiết đều tồn tại trong Unicode. Bình thường hóa có thể giải quyết điều này, mặc dù số lượng âm tiết riêng biệt là khá lớn. Sử dụng NFC/NFKC có thể không hữu ích cho một trie, nhưng trong trường hợp này, sử dụng NFD/NFKD để phân hủy các âm tiết thành các chữ cái cấu thành sẽ hoạt động.

Một vài điểm không liên quan khác để xem xét:

• Ngoài các điểm garçon/Garcon đã lớn lên, bạn có cote/Cote/Côte/vấn đề côté, mà tất cả đều riêng biệt từ Pháp. Tương tự, các nguyên âm trong tiếng Do Thái và tiếng ả Rập thường không bắt buộc, đôi khi có thể gây ra sự mơ hồ.
• Bảng chữ cái của Nam và Đông Nam Á có thể lớn hơn so với tiếng Anh, gấp đôi kích thước.

---

1. Họ được gọi là nghiêm abugidas, nơi nguyên âm được viết như dấu/điểm nhấn, nhưng sự khác biệt này thường có thể được bỏ qua từ một quan điểm lập trình của xem.

Answer 2

Tôi đã tìm thấy rằng nó hoạt động tốt cho các ngôn ngữ Tây Âu, cũng như cho Cyrillic và nhiều ngôn ngữ khác. Nghĩ lại thì, ngôn ngữ duy nhất tôi gặp rắc rối là tiếng Trung, tiếng Nhật, và các hệ thống chữ viết khác. Và đối với những người đó, trie là vô dụng.

Các giá trị Unicode tuần tự của các ký tự tiếng Anh không thực sự là một lợi ích to lớn. Mặc dù gợi ý triển khai nút đơn giản:

CharNode 
    char 
    array[26] of CharNode 

Cấu trúc đó không đặc biệt hữu ích. Nó có thể làm cho mọi việc nhanh hơn, nhưng với chi phí bộ nhớ khá cao. Ngay cả ở cấp độ thứ hai của một trie, mảng đó là đáng kể thưa thớt. Vào thời điểm bạn đạt đến cấp độ thứ tư hoặc thứ năm, nó gần như tất cả không gian chết. Tôi đã phân tích điều đó tại một thời điểm. Tôi sẽ nhìn xung quanh và xem tôi có còn số không.

Tôi đã tìm thấy nó gần như nhanh chóng để có một mảng có độ dài thay đổi trong nút, với các mục được sắp xếp theo tần suất. Ngoài cấp độ thứ hai hoặc thứ ba của bộ ba, nhân vật mà tôi đang tìm kiếm hầu như luôn ở vị trí thứ nhất hoặc thứ hai trong mảng đó. Và tiết kiệm không gian khá lớn. Thay vì 26 tham chiếu cho mỗi nút (104 byte trong thực hiện của tôi), tôi đã có một số byte, và sau đó năm byte cho mỗi tham chiếu. Vì vậy, miễn là có ít hơn 21 trẻ em cho một nút cụ thể (đó là phần lớn thời gian), tôi đã tiết kiệm không gian. Có một hình phạt thời gian chạy nhỏ, nhưng không đủ trong ứng dụng của tôi cho vấn đề.

Đó là sửa đổi duy nhất tôi phải thực hiện cho cấu trúc trie của mình để làm cho nó hỗ trợ tất cả các ngôn ngữ chữ cái mà tôi đang làm việc. Như tôi đã nói, tôi đã làm việc chủ yếu với các ngôn ngữ Tây Âu, và cho những người làm việc rất đẹp. Tôi biết rằng nó đã làm việc với tiếng Do Thái và tiếng Ả Rập, nhưng tôi không biết làm thế nào cũng nó hoạt động. Nó đáp ứng các mục đích của chúng tôi, nhưng liệu nó có hài lòng với người bản xứ không được biết đến hay không.

Bộ ba mà tôi đã xây dựng đã hoạt động đủ tốt cho mục đích của chúng tôi với bất kỳ ngôn ngữ nào có các ký tự phù hợp với Mặt phẳng đa ngôn ngữ Unicode cơ bản. Có một chút kỳ quặc khi làm việc với các cặp thay thế, nhưng chúng tôi đã bỏ qua rất nhiều điều đó.Về cơ bản, chúng tôi chỉ đối xử với cặp thay thế là hai nhân vật và để cho nó đi vào đó.

Bạn phải quyết định xem bạn có muốn xử lý các ký tự có dấu trọng âm dưới dạng các ký tự riêng biệt hoặc nếu bạn muốn ánh xạ chúng. Hãy xem xét, ví dụ, từ tiếng Pháp "garçon", mà một số người sẽ đánh vần "garcon", hoặc bởi vì họ không biết bất kỳ tốt hơn hoặc họ không biết làm thế nào để làm cho nhân vật 'ç'. Tùy thuộc vào những gì bạn đang sử dụng trie cho, bạn có thể tìm thấy nó hữu ích để chuyển đổi ký tự có dấu cho tương đương không có dấu của họ. Nhưng tôi cho rằng đó là nhiều hơn của một vấn đề làm sạch đầu vào hơn là một vấn đề trie.

Đó là cách khá dài của tôi để nói rằng một trie chuẩn sẽ hoạt động tốt cho bất kỳ ngôn ngữ chữ cái nào, mà không có bất kỳ sửa đổi ngôn ngữ cụ thể nào. Tôi không thấy bất kỳ cách rõ ràng nào để sử dụng một trie cho một ngôn ngữ logographic. Tôi không biết gì về Hangul Hàn Quốc, vì vậy tôi không thể nói liệu một trie sẽ có ích ở đó không.