Ograniczenia i alternatywy dla prób w językach innych niż angielski?

Question

Struktura danych Trie często jest świetnym sposobem na przechowywanie napisów w języku angielskim. Działa poprzez budowanie drzewa, w którym każda krawędź jest oznaczona literą, a ścieżka do zaznaczonego węzła w drzewie oznacza jedno ze słów w strukturze danych.

Ta struktura danych działa dobrze w języku angielskim, ponieważ w alfabecie angielskim jest "tylko" 26 liter ("rozsądny" współczynnik rozgałęzienia), znaki te mają kolejne wartości ASCII (więc wskaźniki potomne mogą być przechowywane w postaci tablicy z kluczami według indeksu liter używanych przez każde dziecko) i istnieje wiele angielskich słów ze wspólnymi przedrostkami (więc w strukturze jest dużo redundancji).

Jestem native speakerem z angielską jedynie ograniczoną znajomością innych języków i alfabetów, ale wydaje się, że wiele z tych właściwości nie ma innych języków. Wiem, że na przykład francuski, hiszpański, niemiecki i węgierski często używają znaków diakrytycznych, które nie są przechowywane w sposób ciągły z pozostałymi literami w przestrzeni Unicode. Hebrajski i arabski mają oznaczenia samogłosek, które są zwykle wskazane powyżej lub poniżej każdej litery. Chińczycy używają systemu logogramów, a koreańskie znaki Hangul składają się z trzech małych grup zgrupowanych razem.

Czy próby nadal działają dobrze w przypadku danych przechowywanych w tych językach i alfabetach? Jakie zmiany, jeśli są potrzebne, są niezbędne w przypadku prób użycia tego rodzaju danych? Czy istnieją struktury danych, które działają dobrze na ciągi znaków w tych językach i alfabetach, które są dla nich szczególnie odpowiednie, ale czy nie byłyby przydatne lub wydajne w języku angielskim?

Answer 1

Jako dodatek do odpowiedzi @ JimMischela, chciałbym poruszyć kwestię, że w innych językach często istnieje wiele równoważnych sposobów napisania tego samego. Vietnamese (oparty na alfabecie łacińskim/angielskim) jest szczególnie dobrym przykładem, gdy litery z dwoma akcentami są wspólne. Na przykład Ặ (U + 1EB6) może technicznie również być napisane z sekwencjami Ă + kropka, Ạ + breve, A + breve + kropka, A + kropka + breve.

Unicode normalization może rozwiązać ten problem, przekształcając ciąg znaków w znormalizowany porządek kanoniczny. Dostępne są 4 różne odmiany, NFC, NFKC, NFD i NFKD. Nie będę tutaj zbyt szczegółowo omawiał, ale pierwsze dwa to "złożone formy", które mają tendencję do skracania łańcucha, grupowania podstawowych znaków z akcentami, podczas gdy ostatnie dwa to "formy rozłożone", robiąc coś przeciwnego.

Hangul to interesujący przypadek: jest to alfabet, chociaż wszystkie litery sylaby są zapisane razem w bloku. Zarówno pojedyncze litery, jak i bloki sylabiczne istnieją w Unicode. Normalizacja może rozwiązać ten problem, chociaż liczba wyraźnych sylab jest dość duża. Używanie NFC/NFKC może nie być użyteczne dla trie, ale w tym przypadku użycie NFD/NFKD do rozłożenia sylab do liter składowych zadziała.

Kilka innych niepowiązanych punktów do rozważenia:

• Oprócz punktu garçon/Garcon już wychowany, masz cote/coté/Cote/problemu Cote, które są odrębne francuskie słowa. Podobnie znaki samogłoskowe w języku hebrajskim i arabskim zazwyczaj nie są obowiązkowe, co może czasem powodować niejasności.
• Alfabety z Azji Południowej i Południowo-Wschodniej mogą być duże w porównaniu z angielskim, z grubsza dwa razy większe.

---

1. są ściśle określane abugidas, gdzie samogłoski są zapisywane jako znaki diakrytyczne/akcentami, ale to rozróżnienie można zazwyczaj ignorowane z punktu widzenia programowania.

Answer 2

Odkryłem, że próby sprawdzają się zarówno w językach zachodnioeuropejskich, jak iw cyrylicy i wielu innych językach alfabetycznych. Pomyślcie o tym, jedynymi językami, z którymi miałem problemy były chińskie, japońskie i inne systemy pisma logograficznego. A dla nich trie było bezużyteczne.

Sekwencyjne wartości Unicode znaków angielskich nie są tak naprawdę wielką korzyścią. Chociaż sugeruje prostą implementację węzła:

CharNode 
    char 
    array[26] of CharNode 

Ta struktura nie jest szczególnie pomocna. Może sprawić, że rzeczy będą szybsze, ale przy dość wysokim koszcie pamięci. Nawet na drugim poziomie trie, ta tablica jest wyjątkowo skąpa. Do czasu, gdy dojdziesz do czwartego lub piątego poziomu, to prawie cała martwa przestrzeń. Zrobiłem analizę tego w pewnym momencie. Rozejrzę się i zobaczę, czy nadal mam numery.

Zauważyłem, że niemal tak szybko jest mieć tablicę o zmiennej długości w węźle, z elementami uporządkowanymi według częstotliwości. Poza drugim lub trzecim poziomem trie, postać, której szukałem, znajdowała się prawie zawsze na pierwszej lub drugiej pozycji w tej tablicy. A oszczędność miejsca była dość duża. Zamiast 26 referencji na węzeł (104 bajty w mojej implementacji), miałem jedną liczbę bajtów, a następnie pięć bajtów na odniesienie. Tak długo, jak było mniej niż 21 dzieci dla danego węzła (który był przez większość czasu), zaoszczędziłem miejsce. Wystąpiła niewielka kara za uruchomienie, ale w moim wniosku nie ma znaczenia.

To jedyna modyfikacja, którą musiałem wprowadzić w mojej strukturze trieta, aby mogła obsługiwać wszystkie języki alfabetyczne, z którymi współpracowałem. Jak już powiedziałem, pracowałem głównie z zachodnioeuropejskimi językami, a dla tych, którzy pracowali pięknie. Wiem, że działało z hebrajskim i arabskim, ale nie wiem, jak to działało. Spełnił nasze cele, ale to, czy zaspokoiłoby rodzimego użytkownika, jest nieznane.

Tria, którą zbudowałem, działała wystarczająco dobrze dla naszych celów z każdym językiem, którego postacie mieszczą się w Unicode Basic Multilingual Plane. Podczas pracy z zastępczymi parami było trochę dziwactwa, ale ignorowaliśmy je.Zasadniczo, po prostu potraktowaliśmy zastępczą parę jako dwie postacie i pozwoliliśmy sobie na to.

Musisz zdecydować, czy traktować znaki akcentowane jako osobne znaki, czy też chcesz je zamapować. Rozważmy na przykład francuskie słowo "garçon", które niektórzy ludzie będą oznaczać "garcon", ponieważ nie znają go lepiej lub nie wiedzą, jak stworzyć postać "ç". W zależności od tego, do czego używasz trieka, może się okazać przydatne przekształcanie znaków akcentowanych w ich nieprzypisane odpowiedniki. Ale przypuszczam, że jest to raczej problem z oczyszczaniem danych wejściowych niż problem ze sprzętem.

To mój dość rozwlekły sposób powiedzenia, że ​​standardowy trie powinien dobrze działać dla dowolnego języka alfabetycznego, bez żadnych modyfikacji specyficznych dla języka. Nie widzę żadnego oczywistego sposobu na użycie trieta dla języka logograficznego. Nic nie wiem o koreańskim Hangulu, więc nie mogę powiedzieć, czy trie będzie tam przydatne.