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


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 tablicy z kluczem indeksowanym litery używane 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 języka angielskiego, który ma ograniczoną znajomość 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?


16
2017-12-04 21:29


pochodzenie




Odpowiedzi:


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. wietnamski (oparty na alfabecie łacińskim / angielskim) jest szczególnie dobrym przykładem, gdy litery z dwoma akcentami są wspólne. Na przykład może Ặ (U + 1EB6) technicznie również należy pisać z sekwencjami Ă + kropka, Ạ + breve, A + breve + kropka, A + kropka + breve.

Normalizacja Unicode 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 ciekawy 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 niespokrewnionych punktów do rozważenia:

  • Oprócz punktu garçon / garcon, który już został podniesiony, masz problem cote / cote / côte / côté, które są wyrazistymi francuskimi słowami. Podobnie znaki samogłoskowe w języku hebrajskim i arabskim zazwyczaj nie są obowiązkowe, co może czasem powodować niejasności.
  • Alfabety1 Południowej i południowo-wschodniej Azji może być duża w porównaniu do angielskiej, z grubsza dwa razy większa.

  1. Są ściśle określone abugidas, gdzie samogłoski są zapisywane jako znaki diakrytyczne / akcenty, ale to rozróżnienie zwykle można zignorować z punktu widzenia programowania.

8
2017-12-15 03:55





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 prawie 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 była jedyna modyfikacja, którą musiałem wprowadzić w strukturze mojej gry, aby wspierać wszystkie języki alfabetyczne, z którymi 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 dobrze zadziałało. Spełnił nasze cele, ale to, czy zaspokoiłoby rodzimego użytkownika, jest nieznane.

Trie, które zbudowałem, działało 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 chcesz traktować znaki akcentowane jako oddzielne znaki, czy też chcesz je zmapować. 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 jest 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.


11
2017-12-04 22:07



Po oczyszczeniu danych wejściowych dla systemów zapisu logograficznego wydaje się, że pomocne może być wykorzystanie romanizacji. - Nuclearman
@Nuclearman: Przypuszczam, że romanizacje mogłyby pomóc, jeśli masz dobry słownik. Nigdy nie zastanawiałem się nad tym. Ciekawy pomysł. - Jim Mischel
Innym podejściem jest zanotowanie, że każdy znak może zostać wygenerowany za pomocą określonych kombinacji klawiszy na klawiaturze zaprojektowanej dla tego języka. Powinno być możliwe wykonanie odwrotnego wyszukiwania w celu znalezienia konkretnej kombinacji. Chociaż wymaga to również pewnego rodzaju słownika. - Nuclearman