Trước nay anh chủ yếu chỉ sắp xếp danh sách mà mỗi dòng chỉ có duy nhất một từ (âm tiết). Hầu như không có vấn đề gì nếu chọn đúng locale. Rồi đến một ngày mưa nọ, khi phải xếp lại danh mục từ của một từ điển thì mới thấy có gì đó sai sai.
Ví dụ minh hoạ
Vì trên MacOS không hỗ trợ locale tiếng Việt nên anh phải sử dụng thư viện PyICU và dùng nó như thế này:
import re from icu import Collator, Locale collator = Collator.createInstance(Locale(‘vi_VN.UTF-8’)) lines = [‘Hà Giang’, ‘Hà Nam’, ‘Hà Nội’, ‘Hà Tĩnh’, ‘Hải Dương’, ‘Hải Phòng’, ‘Hậu Giang’, ‘Hoà Bình’, ‘Hưng Yên’] lines = sorted(lines, key=collator.getSortKey)
Với danh sách trên thì ra kết quả đúng:
Hà Giang Hà Nam Hà Nội Hà Tĩnh Hải Dương Hải Phòng Hậu Giang Hoà Bình Hưng Yên
Nhưng nếu thêm “Hạ Long” vào và xếp lại thì nó lại ra như này:
Hà Giang Hạ Long Hà Nam Hà Nội Hà Tĩnh Hải Dương Hải Phòng Hậu Giang Hoà Bình Hưng Yên
Đáng lẽ “Hạ Long” phải đứng sau “Hà Tĩnh” thì nó lại nhảy lên trước cả “Hà Nam”. Còn nếu danh sách chỉ gồm âm tiết đầu thì “Hạ” sẽ đứng sau “Hà” và trước “Hải”, như thế là đúng.
Hà Hà Hà Hà Hạ Hải Hải Hậu Hoà Hưng
Nếu danh sách chỉ vài chục dòng (cùng lắm là vài trăm), chỉ phải làm một lần và có thể kiểm tra thủ công thì câu chuyện dừng lại ở đây. Còn nếu đây là danh sách động và/hoặc có hàng nghìn dòng, hoặc thường xuyên phải làm danh sách thì lại phải tính.
Làm thêm cái bánh xe
Nếu trong danh sách trên mà cho thêm cả “Hạ Trì” thì nó lại đứng sau cả “Hà Tĩnh” (và như thế là đúng). Như vậy thì có vẻ như… À mà cũng không biết như thế nào nữa.
Vì nếu cứ xếp danh sách mà mỗi dòng chỉ có một từ thì nó sẽ chính xác, nên là anh sẽ tìm cách chia ra để xếp như thế. Miễn là nó chạy :v
Và đây là cái bánh xe của anh:
def mwsort(lines : list, by_last_word : bool=False, level : int = 0) -> list: “”” Sort a list by Vietnamese order, each item (or line) may has more than one word. Parameters – lines : list, required To be sorted list by_last_word : bool, optional Order by the last word level : int, auto Recursion level (max is 10) Returns – list The sorted list “”” maxlevel = 10 level += 1 # Each line will be split at the first space # (or the last one if sorting by last word) # # Lines with the same first word with be grouped into # a dict value which the key is the first word groups = {} # And the keys will be grouped into another list keys = [] for line in lines: if level == 1: # Separate hyphens line = re.sub(r”s?-s?”, ” – “, line) line = re.sub(r”s+”, ‘ ‘, line) line = line.strip() if by_last_word: array = line.rsplit(” “, 1) # Split at the last space array.reverse() else: array = line.split(” “, 1) # Split at the first space key = array[0] if key not in groups: # Add a new key-value pair groups[key] = [] keys.append(key) if len(array) > 1: # Append the second part into the dict value groups[key].append(array[1]) else: # This line has one word only groups[key].append(”) # Sort the second parts for k in groups: if level < maxlevel and re.search(” “, ”.join(groups[k])): groups[k] = mwsort(groups[k], level, by_last_word) else: groups[k] = sorted(groups[k], key=collator.getSortKey) # Sort the keys keys = sorted(keys, key=collator.getSortKey) # Create sorted list by the sorted keys sorted_lines = [] for k in keys: for w in groups[k]: # Restore the line if by_last_word: l = ‘ ‘.join([w, k]) else: l = ‘ ‘.join([k, w]) # Normalize hyphens l = l.replace(” – “, ‘-‘) sorted_lines.append(l.strip()) return sorted_lines
So với cách sắp xếp chỉ bằng sorted thì cách này sẽ chậm hơn. Nhìn qua cũng thấy là thời gian xử lí sẽ tỉ lệ thuận với khối lượng dữ liệu đầu vào.
Chạy thử với danh sách họ tên (mỗi dòng có 3 – 4 từ, tức là max level = 3)
Như vậy là trong thử nghiệm trên, mwsort chạy chậm hơn từ 1,5 đến 8 lần so với sorted. Vì dữ liệu thử nghiệm thì chỉ có 2000 dòng khác nhau nên thực tế có thể còn lâu hơn. Dữ liệu càng khác biệt thì càng thêm nhiều vòng lặp.
Nhưng chắc là sắp xếp họ tên thì cũng không quá lâu vì số lượng họ cũng có hạn :p
Trong các ứng dụng web thông thường thì có lẽ danh sách cho mỗi lần xử lí chỉ khoảng vài chục đến vài trăm dòng. Khi đó, thời gian xử lí thêm là không đáng kể. Và điều quan trọng nhất là nó đúng.
Chẳng những thế, anh còn có thể xếp theo tên được nữa chứ.
Mở rộng sang danh sách nhiều cột (bảng)
Như vậy là vấn đề có vẻ cũng dễ dàng, cứ chạy vòng vòng mãi cũng xong.
Nhưng thực tế thì nhân loại thường lập danh sách gồm nhiều cột và cần sắp xếp theo một cột nào đấy (và cũng thường là cột “Họ tên”).
Cũng áp dụng chiến thuật cũ, mình chuyển bảng đó thành một dict. Trong đó key là chuỗi họ tên, còn value là một list với các phần tử là toàn bộ dòng tương ứng với key. Sở dĩ phải dùng list là vì đôi khi cũng có nhiều người có họ tên trùng nhau, nếu không cho vào list thì sẽ bị trùng key và bị ghi đè dữ liệu.
Tiếp theo vẫn là sắp xếp các key này bằng mwsort. Sau cùng là chạy vòng lặp để tạo bảng có thứ tự như ý muốn.
def mcsort(table : list, col : int = 0, by_last_word: bool = False) -> list: “”” Sort a multi-dimensional list (table) in Vietnamese order and based on a specific column Parameters – table : list, required To be sorted multi-dimensional list col : int, optional column or n-th element of each `table` element (zero-based) by_last_word : bool, optional Order by the last word Returns – list The sorted list “”” #pprint(table) dic = {} length = len(table) – 1 for row in table: key = row[col].strip() key = re.sub(r”s+”, ‘ ‘, key) # Normalize hyphens key = re.sub(r”s?-s?”, “-“, key) if key not in dic: dic[key] = [row] else: dic[key].append(row) lines = dic.keys() lines = mwsort(lines, by_last_word) sorted_table = [] for l in lines: for r in dic[l]: sorted_table.append(r) return sorted_table
Đánh giá chung
Vì học hành lõm bõm và không đủ kiên nhẫn để tìm các giải pháp có sẵn nên có thể những gì anh làm ở trên chỉ là thừa thãi. Nói thật là trông nó cũng hơi thủ công, theo kiểu miễn là nó chạy.
Vấn đề xử lí dấu nối (-) cũng đáng cân nhắc vì mwsort làm thay đổi dữ liệu so với ban đầu. Nếu muốn giữ nguyên dữ liệu thì nên dùng mcsort ngay cả với danh sách chỉ có một cột.
Tuy nhiên, với kinh nghiệm tra từ điển tiếng Việt trên dưới hai thập kỉ rưỡi thì anh nghĩ là về cơ bản là đoạn Python trên sẽ cho ra kết quả đúng. Nhưng nếu chẳng may vẫn có sai sót thì anh cũng hoàn toàn không chịu trách nhiệm.
Dù sao anh vẫn chỉ là một người chụp ảnh :v
