30/09/2018, 18:19
Chuyển đổi chuỗi ký tự dựa trên bảng ánh xạ, nhờ mọi người góp ý data structure tối ưu
Ví dụ có 1 bảng ánh xạ như thế này (mình dùng file ini):
[Set]
#key=value
abc=123
ab=19
xyzdd=789abe
defpo=456lkj
Và một chuỗi như thế này:
abcdefpoabcxyzdd
Chuyển đổi theo bảng trên thì được như thế này (nếu có chuỗi con như ab và abc thì chỉ lấy chuỗi dài nhất thôi):
123 456lkj 123 789abe
Mình cần chuyển đổi một lượng khá lớn dữ liệu như vậy dựa theo bảng ánh xạ kiểu như trên. Hiện mình chỉ nghĩ ra được một cấu trúc dữ liệu linked list như thế này (Code C#):
class CharNode
{
Dictionary<char, CharNote> next;
String value;
}
Mình sẽ đưa từng ký tự của phần key trong file ini vào biến next, đến ký tự cuối thì lưu phần value vào biến value để xây dựng data structure. Khi chuyển đổi thì đọc từng ký tự trong chuỗi đầu vào và tìm dần dần vào sâu trong biến next, khi không còn ký tự nào để vào sâu nữa thì biến value chính là chuỗi đích để chuyển đổi.
Nhờ mọi người góp ý là liệu có còn data structure và thuật toán nào tối ưu hơn không, c++ hay c# đều được
Bài liên quan
Up, không ai giúp hết à?
ta thấy vậy cũng ổn rồi, cách này là xây 1 cái finite state machine, như vậy chỉ cần lướt 1 vòng của dữ liệu là xong, vậy là lẹ nhất rồi.
nếu bảng ánh xạ nhỏ và dữ liệu là chuỗi utf-8 (hoặc chỉ thuần ascii) thì có thể xài 1 mảng CharNode next[256] thay cho cái Dictionary, lẹ hơn khi truy next[], nhưng lướt trên chuỗi utf-8 thì dài hơn utf-16 (nếu có ký tự unicode, còn thuần ascii thì ko sao), thành ra có thể lâu hơn. Phải chạy thử mới biết được.