Muszę dopasować ciąg wejściowy do zestawu prefiksów. Mecz powinien być najlepszy z możliwych, na przykład, jeśli są oba abcd* i abcde*, następnie abcdef powinno pasować abcde*. Używam do tego Trie. Problemem jest znak na wejściu, aw zestawie prefiksów może być dowolny znak Unicode. Tak więc tablica potomna, którą mamy w prostym trie, nie będzie możliwa (nie będzie wystarczająco wydajna, przynajmniej, ponieważ rozmiar tablicy będzie bardzo duży). Używanie mapy zamiast tablicy nadal byłoby nieefektywne. Jak powinienem zająć się tym problemem?
Odpowiedzi:
3 dla odpowiedzi № 1Aby zbudować trie, możesz zakodowaćCiągi Unicode jako utf-8, a następnie skonstruuj trie z zakodowanymi sekwencjami bajtów. Lub możesz pracować z punktami kodowymi i użyć mapy skrótów w swoich węzłach. Musisz przetestować swoją aplikację, aby dowiedzieć się, które podejście działa najlepiej.
Ale trudny problem polega na tym, jak zdecydować, kiedy dwa ciągi pasują.
Zastanów się nad słowem kawiarnia
Można to przedstawić jako:
A = [U+0063 U+0061 U+0066 U+0065 U+0301] (kończy się na mi i a łącząc akcent)
Ale także jako
B = [U+0063 U+0061 U+0066 U+00E9] (kończyć z mi, połączony formularz)
Więc:
Jeśli ciągi pasują do przedrostka kawiarnia (bez akcentu)? ZA zaczyna się od tego prefiksu, b nie robi. Jednak ZA i b oba powinny pasować do przedrostka lub nie, ponieważ oba reprezentują to samo słowo kawiarnia.
A co jeśli masz ZA w twoim trie, a ty próbujesz dopasować b? To to samo słowo, więc czy powinno pasować?
→ Być może będziesz musiał przekonwertować ciągi na to samo znormalizowana forma podczas wkładania trie i dopasowywania.Są inne problemy. W języku niemieckim podwójne s jest zwykle pisane jako ß. Powinno ß i ss pasuje czy nie?
I to trwa. Samo podjęcie decyzji, czy dwa ciągi Unicode są równe, jest nietrywialnym problemem. To Ty decydujesz, jak skomplikowane ma być dopasowanie, zależy to od twojej aplikacji.