Швидкі алгоритми сортування та пошуку рядків
Програми для рядків
В основі швидкого сортування та трійкових дерев пошуку лежать добрі старі ідеї, що дозволяють побудувати теоретично ефективні алгоритми. Їхня корисність для випадку, коли ключі є рядками, пройшла практично непоміченою. Шкода! - адже текстові ключі такі поширені в практичних додатках. У цьому розділі ми показуємо, як ідея троїчної рекурсивної декомпозиції, що застосовується до рядків посимвольно, призводить до елегантних та ефективних програм на Сі, які реалізують сортування та пошук рядків. У цьому полягає основний практичний внесок цієї статті.
Ми припускаємо, що читач знайомий із мовою програмування Сі; його "Біблією" є книжка Кернігана та Річі [10]. У Сі символи представляються кодами - цілими числами, які легко порівнювати. Рядки представляються векторами із символів. Структури та теореми, наведені раніше, застосовуються безпосередньо до множин рядків фіксованої довжини. Стандарт Сі, однак, передбачає і рядки з нефіксованою довжиною: кінець такого рядка позначається спеціальним null-символом, код якого - ціле числонуль.
Побудуємо функцію Сі для швидкого сортування рядків (див. додаток А). Головна функція, що сортує, має наступний прототип:
У ній передається масив x з n покажчиків на символьні рядки; вона повинна переставити покажчики таким чином, щоб рядки були розташовані у лексикографічному порядку. Ми введемо другу функцію, параметрами якої будуть обидва ці аргументи плюс додатковий аргумент цілого типу h, що відповідає за "глибину" порівнянь - номери символів, що порівнюються. Алгоритм зупиняється, коли вхідний вектор містить не більше одного рядка, або коли поточна глибина вийде за межінаявних рядків.
У сортуючій функції використовується наступний допоміжний макрос.
Макрос swap переставляє два покажчики в масиві, а макрос i2c («ціле символ») повертає символ "глибини" h рядка x[i]. Функція vecswap переміщає послідовності однакових елементів з їх часових положень у кінцях масиву на потрібні місця у середині.
Повний алгоритм сортування ви знайдете у програмі 1; він близький до коду, представленого Бентлі та Макілроєм [2]. Викликаюча функція алгоритму:
Після розбиття ми рекурсивно сортуємо сегменти більших і менших, а сегмент рівних сортуємо, якщо відповідний символ не дорівнює нулю.
4.15), ключі в середньому мають довжину 22.5 символів. На машинах MIPS, наше оптимізоване сортування виявилося на 20 відсотків швидше за розрядне сортування; на машинах Intel, вона на кілька відсотків повільніша. Швидке сортування зі складовими ключами може виявитися швидше за розрядне сортування і в інших ситуаціях.
Основною проблемою при застосуванні порозрядних сортувань є випадок, коли число наявнихрізнихключів набагато менше їхможливогочисла (або через те, що всі ключі однакові, або тому, що їх мало) . Швидке сортування зі складовими ключами можна розглядати як порозрядне сортування, адаптоване до цієї ситуації за рахунок невеликого збільшення роботи в ситуації, коли кількість різних ключів близька до їх можливого числа.
Звернемося до реалізації таблиці імен з урахуванням трійкових дерев пошуку, зображених малюнку 2. Кожен вузол цього дерева представлений наступною структурою мови Си:
У вузлі зберігається розщеплююче значення splitchar і три покажчики на піддерев'я. Корінь дерева оголошений як Tptr root;
Програма 2. Пошук у троїчномудереві
Програма 2 повертає 1, якщо рядок s є у дереві, і 0 інакше. Вона починає з кореня і спускається вниз по дереву. Гілки lokid та hikid очевидні. Перед тим, як піти гілкою eqkid, програма дивиться на поточний символ і повертає 1, якщо він є символом кінця рядка 0. Після закінчення циклу ми знаємо, що пройшли дерево, але все ще знаходимося в межах рядка, так що повертаємо 0.
Програма 3 вставляє в дерево новий рядок (і нічого не робить, якщо вона там вже є). Оператор root = insert (root, s) вставляє рядок s. Перша гілка if спрацьовує, коли зустрінуто кінець дерева. І тут створюється новий вузол, він ініціалізується, після чого працює регулярна частина. У наступному коді береться відповідна гілка, але гілка до eqkid спрацьовує, тільки якщо рядок ще не закінчився.
Ми тестували пошук на тому ж словнику, що використовувався для тестування сортування. Ми вставили кожне з 72275 слів у дерево, а потім виміряли загальну кількість гілок, взятих по всіх можливих успішних пошуках у дереві. Результати представлені у наступній таблиці:
Рядки описують шість різних способів вставлення рядків у дерево. Для першого шпальти пропонується наступна теорема.
Теорема 11 . Кількість вузлів у трійковому дереві пошуку визначається сукупністю вузлів і залежить від порядку, у якому вузли вставляються.
Доведення . Відповідність між безліччю префіксів рядків та безліччю вузлів дерева взаємно однозначно: кожному префіксу рядка відповідає вузол у дереві та навпаки. Відносні положення вузлів у дереві можуть змінюватись в залежності від порядку введення, проте кількість вузлів постійно.
Зверніть увагу, що у стандартного бору пошуку (без ущільнення вузлів) буде те самекількість вузлів. У використаній для експериментів безлічі даних кількість вузлів становить лише близько 41 відсотка від кількості символів.
Середня довжина слова (включаючи роздільники) складає 696436/72275 9.64 символів. Середня кількість гілок "рівно" при успішному завершенні (успішному) пошуку дорівнює приблизно 9.64, так як кожен символ, що вводиться, порівнюється з рівним елементом один раз. Збалансоване дерево як корінь піддерева завжди вибирає медіану цього набору. У такому дереві кількість надлишкових ("менше" і "більше") порівнянь дорівнює лише 8.30 (близько половини кордону для гіршого випадку, що дорівнює 16, згідно з теоремою 5), так що загальна кількість порівнянь становить якраз 17.94.
Щоб побудувати турнірне дерево, ми спочатку сортуємо безліч, що вводиться. Рекурсивна функція вставляє серединний рядок з його підмасиву, а потім рекурсивно будує лівий та правий підмасив. У цьому дереві використовується приблизно на вісім відсотків порівнянь більше, ніж у збалансованому. У випадковому дереві використовується лише п'ятнадцять відсотків порівнянь більше.
Четвертий рядок таблиці визначає вставку слів у словниковому порядку (без упорядкування за великими літерами та особливими знаками). Два останні рядки описують вставку рядків у порядку сортування та у зворотному сортуванні порядку. При цьому пошук уповільнюється не більше ніж у чотири рази; у бінарному дереві пошуку вони пошук уповільнюється більш ніж у 2000 разів. Потрійні дерева пошуку виявилися цілком стійкими.
Ми провели прості експерименти, порівнюючи троїчне дерево пошуку з іншими описаними батогом [11] структурами, призначеними для ведення таблиць імен. Ми спершу досліджували бінарний пошук, який можна розглядати як реалізацію збалансованих двійкових дерев. Для того жсамої вхідної множини бінарний пошук у середньому використовує 15.19 порівнянь рядків, і досліджує 51.74 символи (у середньому при кожному порівнянні рядків потрібно перевірити 3.41 символів). На всіх комп'ютерах, де ми проводили експерименти, високо оптимізований бінарний пошук вимагав приблизно вдвічі більше часу, ніж програма 2 (на турнірному дереві).
Хешування є своєрідною реалізацією таблиць імен. Щоб уявити n рядків, ми використовували хеш-таблиці розміру tablesize = n зі списком для дозволу колізій. Нижченаведена хеш-функція взята з розділу 6.6 "Біблії" Кернігана та Річі [10]; вона досить ефективна і дає добрий розкид.
Ось тіло функції пошуку:
Для більш чесного виміру часу ми замінили функцію, яка порівнює рядки, на inline-код (так що і хешування, і пошук по дереву використовують один стиль кодування).
На тому ж словнику середній успішний хеш-пошук вимагає 1.50 порівнянь рядків (дзвінків функції strcnp) і 10.17 порівнюваних символів (успішний пошук вимагає одного порівняння зі рядком, що зберігається, і половини порівняння з рядком перед нею, яке майже завжди закінчується на першому символі). Крім того, у кожному пошуку треба обчислити хеш-функцію, якою зазвичай доводиться "помацати" кожен символ вхідного рядка.
Вже ці прості експерименти показали, що трійкові дерева пошуку здатні конкурувати з найкращими з відомих алгоритмів таблиць символів. Однак, існує безліч способів ще покращити трійкові дерева пошуку. Функція пошуку у програмі 2 досить ефективна; оптимізація типу, наприклад, збереження різниці між порівнюваними елементами, переупорядкування перевірок та використання регістрів дозволяють виграти близько десяти відсотків. Ось таблиця, де порівнюється час результуючоїпрограми з аналогічно оптимізованою хеш-функцією:
Числа означають кількість секунд, потрібних для пошуку кожного слова у словнику. Для успішних пошуків обидві структури дають зрівнянні часи. Безуспішні пошуки ми генерували збільшенням на 1 код першого символу в слові (так, слово bat перетворювалося на cat, а слово cat - на неіснуюче слово dat). Потрійні дерева пошуку виявилися швидше хешування як для цієї простої моделі, так і для інших. Моделі для безуспішного пошуку залежать від програми, однак схоже, що трійкові дерева пошуку при безуспішному пошуку виявляться швидше хешування, оскільки вони можуть виявити розбіжності після перевірки кількох перших символів, тоді як у хешуванні бере участь весь ключ.
Для довгих ключів, типових у деяких додатках, перевага навіть більша, ніж у розглянутому тут простому словнику. У багатьох даних бібліотечних запитів DIMACS, наприклад, нашій програмі знадобилося менше однієї п'ятої часу, витраченого хешуванням.
Функція insert у програмі 3 залишає великий простір поліпшення. Вставка за допомогою турнірного дерева (спочатку вставляється медіанний елемент, а потім рекурсивно вставляються менший та більший елементи) представляє розумний компроміс між часом побудови та пошуку. Замінивши виклики функції malloc статичним буфером для розміщення вузлів, ми зведемо практично до нуля час, що витрачається на розподіл пам'яті. Прискорити програму допомагають також інші звичайні методи: перетворення рекурсії в ітерацію, робота з покажчиками на покажчики, переупорядкування перевірок, збереження різниці у порівнянні, і розщеплення одного циклу на два. Об'єднання цих методів прискорило програму 3 вдвічі на всіх розглянутих нами машинах, і набагато сильнішеобладнання з повільним malloc. У наших експериментах ціна вставки всіх слів ніколи не перевищувала ціну пошуку всіх слів за допомогою програми 2 більш ніж на п'ятдесят відсотків. Ефективна програма вставки займає 35 рядків на Сі, її можна знайти на згадуваній раніше Web-сторінці.
Основний недолік трійкових дерев пошуку в порівнянні з хешуванням полягає у їх вимогах до пам'яті. Наше трійкове дерево пошуку використовує 285807 16-байтових вузлів, що в сумі складає 4.573 мегабайти. Хешування використовує хеш-таблицю з 72 275 покажчиків, 72 275 8-байтових вузлів, і 696 436 байтів тексту, що дає 1564 мегабайтів. Інше уявлення трійкових дерев пошуку більш ефективно витрачає пам'ять: коли піддерево містить рядок, ми зберігаємо тільки покажчик на неї (і в кожному вузлі витрачається три біти, які повідомляють, на вказують його нащадки - на вузли або на рядки). Це призводить до більш повільного та складного коду, проте скорочує кількість вузлів у дереві з 285807 до 94952, що ближче до пам'яті, необхідної при хешуванні.
Потрійні дерева пошуку можуть ефективно відповідати на різноманітні запити, що вимагають лінійного часу при використанні хеш-таблиць. Як у більшості впорядкованих дерев пошуку, пошук предків та нащадків даного елемента та підрахунок числа рядків у діапазоні вимагають логарифмічного часу. Аналогічно, прохід дерева дає всі рядки у відсортованому порядку за лінійний час. У наступному розділі ми розглянемо просунуті підходи.
Отже, схоже, що трійкові дерева пошуку поєднують у собі найкращі сторони двох методів: низькі накладні витрати бінарних дерев пошуку (витрата пам'яті та час роботи) та ефективність борів під час роботи із символами. Основна проблема при застосуванні борів на практиці полягає в тому, щоб уникнутивитрати пам'яті майже порожні вузли. Потрійні дерева пошуку можна розглядати як реалізацію борів, елегантно адаптовану для цього випадку за рахунок невеликого збільшення роботи з повними вузлами. Крім того, трійкові дерева пошуку легко реалізовувати; наприклад, порівняйте наш код із реалізацією «хешованих борів» у Кнута [3].
Потрійні дерева пошуку більше року використовуються для представлення англійських словників у комерційній системі Optical Character Recognition (OCR), створеній у Bell Labs. Дерева виявилися швидше хешування, і вони елегантно справляються з 34000-символьним безліччю Unicode Standard. Крім того, розробники експериментували з використанням часткових збігів під час пошуку слів: виявилося, що слід замінювати символи з низькою ймовірністю розпізнавання символом «не має значення», «будь-який».