Стиснення словника. Мови з омонімів та хроматичне число

У природній мові поширене явище, коли для встановлення значення слова необхідно звернутися до контексту.

На грядках росте багато цибулі. / Сильно натягнута тятива лука.

Замок закрили ключем. / Замок оточений ровом.

Ми, як носії мови, цього навіть не помічаємо, адже давно звикли відновлювати значення слів за контекстом — наприклад, вказівних займенників чи поетичних алегорій. До відносно невеликої кількості таких «казусів» з однаковими словами ми також давно звикли, пройшовши безліч мовних ситуацій. У природному середовищі мовна одиниця не існує поза контекстом.

З позиції здорового глузду здається, що кожна окрема річ має мати своє окреме ім'я. Однак, як видно на практиці, у цьому немає необхідності.

У прикладі із замком і луком я пропоную звернути увагу не на сам факт, що для розшифрування значення необхідно звернутися до контексту, а на те, що в мові існує спосіб упакувати два значення в одне слово (далі під словом я розумію токен/мовну одиницю, символ; вважається, що слову не притаманна морфологія).

Розглянемо цей механізм: мені відомо щось про замок (1) і про замок (2), я знаю, що замок (1) відкривається і закривається ключем, висить на стіні тощо, а замок (2) можна побудувати, можна взяти в облогу тощо. Тобто якщо у символу кілька значень і в кожного значення свій контекст, то за контекстом можна однозначно відновити значення, якщо заздалегідь знати їх набір. До речі, замок (1) і замок (2) можуть бути старими або, наприклад, чорними. Але якщо в оточенні слова є інші слова, що стосуються конкретного значення (наприклад, «башти за стіною» або «насилу відімкнувся»), то значення відновлюване. Так ми розуміємо, що перед нами: за́мок чи замо́к.

Перед нами відкривається незвичайна можливість: об'єднувати два значення в один символ — компресія словника через об'єднання слів в омоніми. У цій роботі ми свідомо відмовляємося від однозначності слів. Розглянемо, наскільки природні мови піддаються такому стисненню, і подивимося, як виглядають мови з максимальною кількістю омонімів у словнику.

Механізм стиснення

Задумка в тому, щоб брати множину таких слів, чиї контексти попарно не перетинаються, і позначати їх одним знаком.

Більш формально. Є символ і в нього значень кожному значенню , зіставлено множину контекстів , причому

.

(a) це гарантія того, що значення ідентифіковане. Така структура нашого слова-омоніма.

Тепер, якщо ми вирішили з'єднати два слова і , значення і контексти нового слова будуть і відповідно. Ключовим моментом буде дотримання умови (а), щоб будь-які два значення не мали спільних контекстів і були розрізненні.

Розглянемо межу стиснення, яке може дозволити таке об'єднання. Побудуємо граф , де вершини будуть словами, а ребра означатимуть, що контексти слів перетинаються. Тобто якщо слова з'єднані ребром, то їх вживання схоже, і однозначно відрізнити одне від одного не вийде за наявних контекстів. Якщо об'єднати два схожі слова, то ми не зможемо однозначно встановити значення омоніма. Об'єднати в один символ можна слова без спільних контекстів, тобто слова, не з'єднані ребром. Таким чином, ми прагнемо об'єднати максимальну кількість несуміжних слів одним символом, мінімізуючи загальну кількість символів. А це є хроматичне число графа .

Реалізація

Розберемо деталі реалізації. По ходу демонструватиму висновки на прикладі бази з корпусу російської Вікіпедії.

Стандартна попередня обробка: приведення букв до нижнього регістру, видалення всього, окрім букв нашої мови та пробілів, заміна букви ё на е та видалення зайвих пробілів і переносів рядків. Текст розбивається на слова, і відсікаються ті, що зустрічалися надто рідко. Рідкісні слова далі всюди ігноруються.

from datasets import load_dataset
from tqdm import tqdm

filename = "./base/russian_wikipedia.txt"

ds = load_dataset(
    "wikimedia/wikipedia",
    "20231101.ru",
    split="train",
    streaming=True
)

for item in ds:
    print(item["text"][:500])
    break

with open(filename, "w", encoding="utf-8") as f:
    for i, item in enumerate(tqdm(ds)):
        if i >= 10000:
            break
        f.write(item["text"] + "\n")

from os import walk
import re
from tqdm import tqdm

base_path = './base/'

data_text = ''

for dirpath, dirnames, filenames in walk(base_path):
    for file_name in filenames:
        if file_name[-4:] != '.txt': continue

        print('Read:', file_name)
        try:
            current_text = open(dirpath + '/' + file_name, 'r', encoding='utf-8').read()
            data_text += current_text
        except Exception as e:
            print(f'Error reading {file_name}: {e}')

def prepare_text(text):
    n_text = text.lower()
    n_text = re.sub(r'[^а-яё\s]+', ' ', n_text)
    n_text = re.sub(r'ё', 'е', n_text)
    n_text = re.sub(r'\n+', ' ', n_text)
    n_text = re.sub(r'\s+', ' ', n_text)

    return n_text

data_text = prepare_text(data_text)

alphabet = list(set(data_text))

print('---')
print('Final data length:', len(data_text), 'symbols')
print('Alphabet length:', len(alphabet))
print('Alphabet:', alphabet)
print('Text sample:', data_text[:100])


from collections import defaultdict, Counter
from typing import List, Dict, Set

words = data_text.split()
freq = Counter(words)

min_frequency = 5

vocab = {w for w, c in freq.items() if c >= min_frequency}

print(f"Before word count: {len(freq)}")
print(f"Vocabulary size: {len(vocab)}")

Литва ( ), офіційна назва — Литовська Республіка () — держава, розташована в Північній Європі. Площа —  км². Протяжність з півночі на південь — 280 км, а із заходу на схід — 370 км. Населення становить  чоловік (серпень, 2023). Займає 137-е місце у світі за чисельністю населення і 121-е за територією. Має вихід до Балтійського моря, розташована на його східному узбережжі. Берегова лінія становить лише 99 км (найменший показник серед держав Балтії). На півночі межує з Ла
10000it [00:20, 495.20it/s]

Read: russian_wikipedia.txt
---
Final data length: 110594518 symbols
Alphabet length: 33
Alphabet: ['б', 'о', 'т', 'ы', 'с', 'р', 'ш', 'е', 'ц', 'в', 'й', 'у', 'ф', 'ю', 'п', 'х', 'ч', 'и', 'э', 'м', 'д', 'а', 'ь', 'г', 'ъ', 'я', 'з', 'л', ' ', 'ж', 'н', 'к', 'щ']
Text sample: литва офіційна назва литовська республіка держава розташоване в північній європі площад

Before word count: 592173
Vocabulary size: 163793

Було: 
Литва ( ), офіційна назва — Литовська Республіка () — держава, розташована в Північній Європі. Площ

Стало:
литва офіційна назва литовська республіка держава розташована в північній європі площ

було 592173 слів, після відкидання рідкісних 163793

Контекстом було вирішено вважати невпорядковану множину радіуса слів ліворуч і праворуч від вибраного слова. Отримуємо 13 373 031 різних контекстів для (вікно контексту 4 слова).

Хроматичне число в загальному випадку обчислюється за експоненціальний час, тому ми вдаємося до жадібного алгоритму. Слова сортуються за зростанням частоти. Рідкісні слова отримують клас (символ) першими, оскільки їх контексти перетинаються з меншою ймовірністю. Слова вбудовуються в уже існуючі класи, якщо це можливо, або їм призначаються свої.

from tqdm import tqdm

word_to_id = {w: i for i, w in enumerate(sorted(vocab))}
id_to_word = {i: w for w, i in word_to_id.items()}

context_to_words: Dict[int, Set[int]] = defaultdict(set)

radius = 2

ctx_counter = 0

for i, w in enumerate(tqdm(words[radius:len(words) - radius])):
    if w not in vocab:
        continue

    w_id = word_to_id[w]
    left = max(0, i - radius)
    right = min(len(words), i + radius + 1)

    context_word_ids = set()
    for j in range(left, right):
        if j == i:
            continue
        cand = words[j]
        if cand in vocab:
            context_word_ids.add(word_to_id[cand])

    if not context_word_ids:
        continue

    ctx_key = frozenset(context_word_ids)
    ctx_id = hash(ctx_key)

    context_to_words[ctx_id].add(w_id)

print(f"Total contexts: {len(context_to_words)}")

blocked: Dict[int, Set[int]] = defaultdict(set)

for ctx_id, ctx_words in tqdm(context_to_words.items()):
    ctx_words_list = list(ctx_words)
    for a in ctx_words_list:
        for b in ctx_words_list:
            if a != b:
                blocked[a].add(b)

class_members: List[Set[int]] = []
word_to_class: Dict[str, int] = {}

sorted_words = sorted(vocab, key=lambda x: (freq[x], x))

for w in tqdm(sorted_words):
    w_id = word_to_id[w]

    placed = False
    for class_id, members in enumerate(class_members):
        if not (blocked[w_id] & members):
            members.add(w_id)
            word_to_class[w] = class_id
            placed = True
            break

    if not placed:
        class_members.append({w_id})
        word_to_class[w] = len(class_members) - 1

classes: Dict[int, List[str]] = {}
for w, cls in word_to_class.items():
    classes.setdefault(cls, []).append(w)

for cls in classes:
    classes[cls].sort()

На корпусі Вікіпедії алгоритм породжує 1420 класів. Розподіл вкрай нерівномірний: клас 0 містить 121 703 слова. Це переважна більшість лексики, чиї контексти унікальні й не перетинаються ні з ким. Класи 1–10 містять від 13 305 до 554 слів. Далі розміри класів швидко зменшуються до 1–2 слів.

Це означає, що словник із 163 793 слів стискається до 1420 символів (у ~115 разів, що вражає).

Приклади об'єднань:

Class 405: 4 words
['індикаторів', 'плані', 'розповідь', 'шведському']
---
Class 406: 4 words
['медичному', 'містерій', 'списку', 'хід']
---
Class 407: 4 words
['майбутньому', 'герасимов', 'трохи', 'орехово']
---
Class 408: 4 words
['нагороджений', 'регресія', 'міститься', 'труп']
---
Class 409: 4 words
['новому', 'освіті', 'світліше', 'вугіллям']
---
...
---
Class 884: 2 words
['землі', 'тверді']
---
Class 885: 2 words
['обряди', 'реакції']
---
Class 886: 2 words
['ооо', 'гай']
---
Class 887: 2 words
['записав', 'музика']
---
Class 888: 1 words
['леві']
---
...
---
Class 1413: 1 words
['к']
---
Class 1414: 1 words
['із']
---
Class 1415: 1 words
['по']
---
Class 1416: 1 words
['с']
---
Class 1417: 1 words
['на']
---
Class 1418: 1 words
['і']
---
Class 1419: 1 words
['в']
---

Експерименти

Олександр Пушкін "Казка про царя Салтана"

Російськомовна Вікіпедія

Class 8: 31 words
['серпня', 'квітня', 'б', 'був', 'верховного', 'ветлужський', 'рр', 'німеччини', 'дім', 'завод', 'імперії', 'іркутськ', 'як', 'кіно', 'лв', 'місце', 'мир', 'світу', 'наук', 'область']
---
Class 9: 17 words
['академії', 'біла', 'другої', 'го', 'місто', 'якщо', 'їх', 'млн', 'листопада', 'пам'ять', 'район', 'російський', 'росія', 'вересня', 'сергацький', 'х', 'е']
---
Class 10: 17 words
['богородський', 'століття', 'у', 'грудня', 'його', 'ім', 'імені', 'перший', 'пр', 'району', 'ррфср', 'радянський', 'союзу', 'то', 'тис', 'у', 'федерації']
---
Class 11: 14 words
['велика', 'володарський', 'воскресенський', 'міста', 'для', 'липня', 'й', 'населення', 'близько', 'він', 'п', 'при', 'російської', 'ради']
---
Class 12: 9 words
['великий', 'роки', 'городецький', 'д', 'або', 'років', 'травня', 'я', 'січня']
---
Class 13: 9 words
['день', 'з', 'н', 'області', 'павловський', 'сша', 'т', 'вулиця', 'ум']
---
Class 14: 5 words
['е', 'км', 'березня', 'не', 'ссср']
---
Class 15: 3 words
['рік', 'м', 'р']
---
Class 16: 3 words
['г', 'за', 'росії']
---
Class 17: 1 word
['до']
---
Class 18: 1 word
['від']
---
Class 19: 1 word
['році']
---
Class 20: 1 word
['а']
---
Class 21: 1 word
['к']
---
Class 22: 1 word
['року']
---
Class 23: 1 word
['по']
---
Class 24: 1 word
['с']
---
Class 25: 1 word
['на']
---
Class 26: 1 word
['і']
---
Class 27: 1 word
['в']
---

Англомовна Вікіпедія

Class 31: 6 words
['climbs', 'henry', 'newcomers', 'oxides', 'rivers', 'village']
---
Class 32: 6 words
['aegean', 'bangla', 'dominance', 'language', 'opening', 'prize']
---
Class 33: 6 words
['chin', 'conquered', 'estate', 'largest', 'museum', 'nemesis']
---
Class 34: 6 words
['department', 'geoffrey', 'mike', 'sulfide', 'tri', 'university']
---
...
---
Class 58: 4 words
['battles', 'copper', 'film', 'starring']
---
Class 59: 4 words
['count', 'knight', 'pro', 'war']
---
Class 60: 4 words
['dynasty', 'most', 'store', 'tamil']
---
Class 61: 4 words
['containing', 'from', 'matt', 'medieval']
---
Class 62: 3 words
['faith', 'genus', 'soul']
---
Class 63: 3 words
['der', 'onto', 'winner']
---
Class 64: 2 words
['fly', 'method']
---
...
---
Class 95: 2 words
['north', 'over']
---
Class 96: 1 word
['some']
---
Class 97: 3 words
['all', 'between', 'by']
---
Class 98: 1 word
['or']
---
Class 99: 1 word
['also']
---
Class 100: 2 words
['after', 'one']
---
Class 101: 1 word
['with']
---
Class 102: 1 word
['for']
---
Class 103: 1 word
['as']
---
...

Російськомовна Вікіпедія (лематизована)

Перше, що впадає в око: перший клас забирає переважну більшість слів, далі кількість слів на клас стрімко зменшується. Це означає, що майже всі слова попарно несуміжні (контексти не перетинаються), і лише невелика частка утворює щільні підграфи. Граф дуже розріджений. Хроматичне число визначається кількома щільними кліками слів, які важко розрізнити за контекстом.

Виникла гіпотеза, що необхідність узгоджувати морфологічні ознаки в російській мові забезпечить «пласти» майже непересічних підграфів. Оскільки різні форми одного слова вважалися різними словами, а в російській мові різні категорії необхідно морфологічно узгоджувати, це давало б великий простір для стиснення нашим алгоритмом, адже ці різні форми матимуть свої незалежні контексти. Пласти, наприклад, контекстів, пов'язаних з різними часами, будуть значно менше перетинатися, а отже їх можна буде об'єднувати.

Було вирішено це перевірити, лематизувавши датасет. Очікувалося, що він стискатиметься гірше, оскільки ці «шари морфологічної узгодженості» схлопнуться, і залишиться щільніша структура. На практиці вийшло навпаки: лематизований корпус стиснувся краще (х61 проти х35). При цьому лематизований корпус показує навіть більшу кількість унікальних контекстів. Справа в тому, що разом з формами слів об'єдналися і їхні зв'язки (великого дому, великому дому, ... → великий дім). Більшість таких зв'язків була «паралельною», а приведення всього до лем схлопнуло їх в одну. Зникли зв'язки, які були відправлені з одного слова в різні словоформи, що робили структуру графа густішою. Це зробило його більш розрідженим, що дало більше свободи для стиснення. Це видно за кількістю слів на контекст: 1.03 ± 1.35 в оригінальній проти 1.04 ± 0.65 в лематизованій. Ця характеристика корисна для оцінки можливості стиснення, оскільки слова, що зустрічаються в одному контексті, не можуть бути об'єднані.

При англійська стискається слабше (х22 проти х35). Це виглядає як підтвердження гіпотези: англійська морфологія бідніша: менше форм, більше слів на контекст (1.07 ± 1.71 в англ. проти 1.03 ± 1.35 в рос.), менше вершин, які можна було б склеїти. При великих різниця нівелюється: і там, і там граф стає розрідженим, і хроматичне число визначається вже не морфологією, а функційною лексикою: прийменниками, артиклями, сполучниками, які сполучаються з усім і утворюють кліки, що задають нижню межу.

Перспективи

Метою цієї роботи в першу чергу було дослідження меж стиснення словника природних мов в омонімічні. У подальшому можна було б по-іншому побудувати обробку малочастотних слів, оскільки в представленій реалізації вони просто відкидалися, могли утворюватися менш репрезентативні контексти, які ускладнили б потенційне відновлення значення. Але на цьому етапі я вважаю це несуттєвим. Отримані спостереження вже досить цікаві.

Окрім тем, розібраних у статті, під час її створення у мене виникали суміжні питання, які було б також корисно і цікаво розглянути:

1. Використати отримані класи як алфавіт для шифрування підстановкою. Потрібно розглянути можливість дешифрування. Щоб відновити задумане значення-слово, потрібно розпізнати контекст навколо нього. Але оскільки початкові контексти були природною мовою, відновлювати їх потрібно зі значень класів (яких може бути значно багато). Слід було б починати з нечисленних класів, а далі в гіршому випадку перебрати всі значення символів. Зачіпкою для зниження перебору тут може бути спільна вживаність слів, оскільки в класах часто лежать несумісні одне з одним слова. Це може суттєво знизити перебір. Слова по боках буде складніше перекласти, оскільки їхні контексти будуть менш коректними.

   Я не є фахівцем у криптографії, але мені нещодавно траплялася дуже цікава стаття, в якій розглядався механізм перекладу мови без паралельних джерел як механізм розгадки шифру (deciphering). Це здійснювалося через пошук підстановок слів (заміни слів однієї мови на слова іншої), що максимізує правдоподібність тексту, перекладеного з цією підстановкою. Можливо, подібні методики були б корисні для роботи з таким шифром.

2. Було б цікаво прикинути, наскільки новий словник піддається повторному стисненню. Теоретично контекст таким чином буде розширений через контексти нових символів. Все буде так само зав'язано на початкових контекстах, тільки погляд на них відбуватиметься через призму нових символів. Вікно буде еквівалентне сумі радіусів на всіх ітераціях. Це схоже на композицію згорткових шарів нейромереж.

3. Як добре будуть навчатися і працювати з таким текстом нейронки? Як зміниться ентропія і передбачуваність порівняно з природною мовою? Заміна слів на класи-омоніми знижує ентропію спостережуваної послідовності, зміщуючи фокус з лексики на семантику. Для нейромережі це виглядає як зменшення словника і зникнення довгого хвоста рідкісних слів. Тому такий текст може бути зручним для навчання компактних мовних моделей, але стає більш вимогливим до контекстного механізму і може втрачати лексичну та фактологічну точність. Інформація не зникає: вона переноситься в умовний розподіл вихідного слова відносно класу та контексту.

4. Чи можна, маючи корпус тексту природною мовою, розпізнати серед слів багатозначні? У нашому алгоритмі за значення ми вважали вже самі слова. Для алгоритму неважливо, скільки значень у слова: за будь-якої їх кількості умови розрізненності дотримуються, і алгоритм працює коректно. Але якщо ми поставимо інше питання: чи можна розпізнати значення, властиві символу? По ідеї в символі може бути будь-яка кількість значень, головне, щоб їхні контексти попарно не перетиналися. Тобто для кожного слова ми можемо розглянути потенційних значень (кількість підмножин його контекстів). Але як серед них відбирати валідні "значення"? У першу чергу потрібне більш формальне та адекватне визначення значення. А це питання потребує окремого аналізу.