Наука За Данни И Бази Данни
Структурата на данните Trie: Пренебрегван скъпоценен камък
Още от първите дни в живота ни като програмисти , всички сме се занимавали със структури от данни: Масиви, свързани списъци, дървета, набори, стекове и опашки са нашите ежедневни спътници, а опитен програмист знае кога и защо да ги използва. В тази статия ще видим как една често пренебрегвана структура от данни, трие , наистина блести в домейни на приложения със специфични функции, като игри с думи.
Игри с думи като пример за трие
Като начало, нека разгледаме един прост пъзел с думи: намерете всички валидни думи в табло с 4х4 букви, свързвайки съседни букви хоризонтално, вертикално или диагонално. Например в следващата дъска виждаме буквите „W“, „A“, „I“ и „T“, свързващи се, за да образуват думата „WAIT“.
Наивното решение за намиране на всички думи на valids би било да се изследва дъската, като се започне от горния ляв ъгъл и след това се премине първо към дълбочината към по-дълги последователности, като се започне отново от втората буква в първия ред и т.н. В дъска 4x4, позволяваща вертикални, хоризонтални и диагонални движения, има 12029640 последователности, с дължина от един до шестнадесет символа.
Сега целта ни е да намерим най-добрата структура от данни за прилагане на тази програма за проверка на валидни думи, т.е. нашия речник. Няколко точки, които трябва да имате предвид:
- Нуждаем се само от едно копие на всяка дума, т.е. речникът ни е набор от логическа гледна точка.
- Трябва да отговорим на следните въпроси за дадена дума:
- Текущата последователност от символи съдържа ли валидна дума?
- Има ли по-дълги думи, които започват с тази последователност? Ако не, можем да се откажем от първоначалното ни изследване, тъй като навлизането по-дълбоко няма да даде валидни думи.
За да илюстрирате втората точка, помислете за следната дъска: Няма смисъл да изследвате следващите ходове, тъй като в речника няма думи, които започват с „ASF“.
Ще се радваме структурата ни от данни да отговори на тези въпроси възможно най-бързо. ~ O (1) времето за достъп (за проверка на последователност) би било идеално!
Можем да определим интерфейса на лексиката по този начин (вж тук за репозитория на GitHub):
public interface Vocabulary { boolean add(String word); boolean isPrefix(String prefix); boolean contains(String word); } Trie Структура на данните срещу алтернативи
Прилагане на contains() метод изисква резервна структура от данни, която ви позволява ефективно да намирате елементи, докато isPrefix() методът изисква от нас да намерим „следващия по-голям елемент“, т.е. трябва да поддържаме речника сортиран по някакъв начин.
Можем лесно да изключим хеш-базирани набори от нашия списък с кандидати: макар че такава структура би ни давала постоянна проверка за contains(), тя би се представяла доста лошо при isPrefix(), в най-лошия случай изисква сканираме целия комплект.
По точно обратната причина можем да изключим и сортираните свързани списъци, тъй като те изискват сканиране на списъка поне до първия елемент, който е по-голям или равен на търсената дума или префикс.
Две валидни опции използват сортиран списък, подкрепен с масив, или двоично дърво.
В сортирания списък, подкрепен с масив, можем да използваме двоично търсене, за да намерим текущата последователност, ако има такава, или следващия по-голям елемент на цена от O (log2 (n)) , където н е броят на думите в речника.
Можем да приложим речник, подкрепен с масив, който винаги поддържа подреждане на подобни това , използвайки стандартни java.util.ArrayList и java.util.Collections.binarySeach:
public class ListVocabulary implements Vocabulary { private List words = new ArrayList(); /** * Constructor that adds all the words and then sorts the underlying list */ public ListVocabulary(Collection words) { this.words.addAll(words); Collections.sort(this.words); } public boolean add(String word) { int pos = Collections.binarySearch(words, word); // pos > 0 means the word is already in the list. Insert only // if it's not there yet if (pos = 0) { // The prefix is a word. Check the following word, because we are looking // for words that are longer than the prefix if (pos +1 = 0; } } Ако решим да използваме двоично дърво, внедряването може да бъде още по-кратко и по-елегантно (отново, тук е връзка към кода ):
public class TreeVocabulary extends TreeSet implements Vocabulary { public TreeVocabulary(Collection c) { super(c); } public boolean isPrefix(String prefix) { String nextWord = ceiling(prefix); if (nextWord == null) { return false; } if (nextWord.equals(prefix)) { Set tail = tailSet(nextWord, false); if (tail.isEmpty()) { return false; } nextWord = tail.iterator().next(); } return nextWord.startsWith(prefix); } /** * There is a mismatch between the parameter types of vocabulary and TreeSet, so * force call to the upper-class method */ public boolean contains(String word) { return super.contains(word); } } И в двата случая можем да очакваме O (log n) изпълнение за всеки метод за достъп (contains() и isPrefix()). Що се отнася до изискванията за пространство, както изпълнението, подкрепено от масив, така и изпълнението, подкрепено с дърво O (n + M) където n е броят на думите в речника, а M е байтазът на речника, т.е.сумата от дължината на низовете в речника.
Trie приложения: кога и защо използваме опити
Логаритмичното представяне и линейната памет не са лоши. Но има още няколко характеристики на домейна на нашето приложение, които могат да ни доведат до по-добра производителност:
- Можем спокойно да предположим, че всички думи са с малки букви.
- Приемаме само букви a-z - без пунктуация, без тирета, без ударения и т.н.
- Речникът съдържа много наклонени форми: множествено число, спрегнати глаголи, съставни думи (напр. Къща -> икономка). Следователно, много думи споделят едно и също стъбло .
- Думите имат ограничена дължина. Например, ако работим върху дъска 4x4, всички думи, по-дълги от 16 символа, могат да бъдат изхвърлени.
Тук влиза трие (произнася се „опитай“). Но какво точно е трие? Опитите са пренебрегвани структури от данни, които се срещат в книгите, но рядко в стандартните библиотеки.
За мотивация, нека първо разгледаме детето на плаката на Computer Science: двоичното дърво. Сега, когато анализираме производителността на двоично дърво и казваме операция х е O (log (n)) , ние непрекъснато говорим за регистрационна база 2. Но какво, ако вместо двоично дърво, ние използвахме тройно дърво, където всеки възел има три деца (или фен от три). Тогава ще говорим за дневник база 3. (Това е подобрение на производителността, макар и само с постоянен фактор.) По същество нашите дървета ще станат по-широки, но по-къси и бихме могли да извършим по-малко справки, тъй като не е нужно да слизаме съвсем толкова дълбоко.
Ако направим нещата още по-далеч, какво ще стане, ако имаме дърво с разклонение, равно на броя на възможните стойности на нашия тип данни?
Това е мотивацията зад трие. И както може би се досещате, трие наистина е дърво, триево дърво, така да се каже!
Но, за разлика от повечето бинарни дървета, които бихте използвали за сортиране на низове, тези, които биха съхранили цели думи в техните възли, всеки възел на трие съдържа един символ (и дори не това, както ще видим скоро) и има максимално раздуване, равно на дължината на азбуката. В нашия случай дължината на азбуката е 26; следователно възлите на трие имат максимално разклонение от 26. И докато балансирано двоично дърво има log2 (n) дълбочина, максималната дълбочина на трие е равна на максималната дължина на дума! (Отново по-широк, но по-кратък.)
В рамките на трие, думи с един и същ ствол (префикс) споделят областта на паметта, която съответства на основата.
За да визуализираме разликата, нека разгледаме малък речник, съставен от пет думи. Да приемем, че гръцките букви означават указатели и отбележете, че в трие, червените символи означават възли, съдържащи валидни думи .
Внедряване на Java Trie
Както знаем, в дървото указателите към дъщерните елементи обикновено се изпълняват с лява и дясна променлива, тъй като максималният вентилационен изход е фиксиран на две.
В трие, индексиращо азбука от 26 букви, всеки възел има 26 възможни деца и следователно 26 възможни указатели. По този начин всеки възел разполага с масив от 26 (указатели към) поддървета, където всяка стойност може да бъде нула (ако няма такова дете) или друг възел.
Как тогава търсим дума в трие? Ето метода, който при String s ще идентифицира възела, който съответства на последната буква на думата, ако съществува в дървото:
public LowercaseTrieVocabulary getNode(String s) { LowercaseTrieVocabulary node = this; for (int i = 0; i LOWERCASE.getIndex(s.charAt(i)) метод просто връща позицията на ит знак в азбуката. На върнатия възел, логическо свойство node показва, че възелът съответства на последната буква на дума, т.е.буква, маркирана в червено в предишния пример. Тъй като всеки възел поддържа брояч на броя деца, ако този брояч е положителен, тогава в речника има по-дълги думи, които имат текущия низ като префикс. Забележка: възелът всъщност не трябва да запазва препратка към знака, на който съответства, тъй като това се подразбира в позицията му в трие.
Анализиране на ефективността
Това, което прави структурата на трие наистина ефективна в тези ситуации, е, че цената за търсене на дума или префикс е фиксирана и зависи само от броя на знаците в думата, а не от размера на речника.
В нашия конкретен домейн, тъй като имаме низове, които са най-много 16 знака, са необходими точно 16 стъпки за намиране на дума, която е в речника, докато всеки отрицателен отговор, т.е. думата или префиксът не е в трие, може да бъде получен в най-много 16 стъпки, както добре! Като се има предвид, че преди това сме игнорирали дължината на низа, когато сме изчислявали сложността на текущото време както за сортирания списък, подкрепен с масив, така и за дървото, което е скрито в сравненията на низове, можем също да го игнорираме тук и безопасно да заявим, че търсенето е направено в O (1) време.
Като се вземат предвид изискванията за пространство (и като се помни, че сме посочили с М байтаз на речника), трие може да има М възли в най-лошия случай, ако няма два низа, които да споделят префикс. Но тъй като сме забелязали, че в речника има висока степен на излишък, трябва да се направи много компресия. Английският речник, който се използва в примерния код, е 935 017 байта и изисква 250 264 възли, със степен на компресия около 73%.
Въпреки това, дори това компресирано трие обикновено изисква повече памет, отколкото дърво или масив. Това е така, защото за всеки възел най-малко 26 x sizeof(pointer) са необходими байтове, плюс някои режийни за обекта и допълнителни атрибути. На 64-битова машина всеки възел изисква повече от 200 байта, докато символът на низа изисква един или два байта, ако разгледаме UTF низове.
Свързани: Топ 10 на най-често срещаните грешки, които Java разработчиците допускат: Урок за начинаещи в Java Опити и тестове за ефективност
И така, какво ще кажете за изпълнението? Реализациите на речника бяха тествани в две различни ситуации: проверка за 20 000 000 произволни низове и намиране на всички думи в 15 000 табла, генерирани произволно от същия списък с думи.
Бяха анализирани четири структури от данни: сортиран списък, подкрепен с масив, двоично дърво, трие, описано по-горе, и трие, използващо масиви от байтове, съответстващи на азбучния индекс на самите символи (незначителна и лесно изпълнима оптимизация на производителността). Ето резултатите в ms:
Средният брой движения, направени за решаване на дъската, е 2188. За всяко преместване се извършва търсене на дума и префикс, т.е. за проверка на всички дъски се извършват повече от 32M търсене на думи и 32M префикси. Забележка: това може да се направи в една стъпка, аз ги държах отделени за яснота в изложението. Уплътняването им в една стъпка би намалило времето за решаване на дъските почти наполовина и вероятно би благоприятствало трие още повече.
Както може да се види по-горе, търсенето на думата се представя по-добре с трие, дори когато се използват низове, и е още по-бързо при използване на индекси на азбука, като последните изпълняват повече от два пъти по-бързо от стандартното двоично дърво. Разликата в решаването на дъските е още по-очевидна, като бързото трие-азбучно-индексно решение е повече от четири пъти по-бързо от списъка и дървото.
Обобщавайки
Trie е много специализирана структура от данни, която изисква много повече памет, отколкото дървета и списъци. Когато обаче се прилагат специфични характеристики на домейна, като ограничена азбука и висока излишък в първата част на низовете, това може да бъде много ефективно при адресиране на оптимизацията на производителността.
Препратки
Обширно обяснение на опитите и азбуките може да се намери в глава 5 от книгата на Робърт Седжуик „Алгоритми, 4-то издание“. Придружаващият уебсайт в Принстън има код за изпълнение на Alphabet и TrieST, което е по-обширно от моя пример.
Описание на трие и изпълнения за различни езици също можете да намерите на Уикипедия и можете да погледнете това Ресурс за трие на университета в Бостън както добре.
Свързани: Игла в купа сено: отличен урок за широкомащабен алгоритъм за търсене на текст Разбиране на основите
Какво е трие?
Trie е подредена структура от данни, вид дърво за търсене, използвано за съхраняване на асоциативни структури от данни. Също така се нарича дърво на Radix или дърво на префикс.
Какво е компресирано трие?
Компресираното трие е по същество структура от данни на трие с допълнително правило, че всеки възел трябва да има две или повече деца.
Кое произношение на trie е правилно?
Трие се произнася „опитайте“, въпреки че името трие произлиза от „извличане“.
За какво е полезна структурата от данни на trie?
Структурата от данни на trie е подходяща за съвпадение на алгоритми, тъй като те се основават на префикса на всеки низ. Обикновено се използват опити, когато се работи с групи от низове, а не с отделни низове, което им позволява да решават широк спектър от проблеми.
