Dùng Python xếp danh sách theo bảng chữ cái tiếng Việt

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)

Số dòng	sorted	mwsort
2.000	60ms	90ms
10.000	75ms	200ms
50.000	150ms	800ms
500.000	960ms	7.000ms
1.000.000	1.900ms	14.500ms

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