ternary tree / minimal perfect hash - Исходники

Допустим у нас есть некая таблица(а.к.а. словарь) состоящая из N ключевых слов[1].
Нам нужно написать функцию типа:

  int search(const char* some_word);

которая быстро возвращает либо число из диапазона [1..N] если some_word в таблице или 0 если такого слова там нет.

Задача построения такой функции решаема несколькими вариантами, один из них например
построить т.н. minimal perfect hash function с помощью например gperf (но это возможно не на каждом наборе).

Второй вариант — воспользоваться предлагаемой имплементацией ternary tree [2]:

Класс ternary_tree кроме двух очевидных и полезных методов:

dword ternary_tree::insert(const char* s);
dword ternary_tree::search(const char* s);

имеет также бонус методы:

size_t ternary_tree::partial_match_search(const char *s, array<dword>& result_set );
size_t ternary_tree::neighbour_search(const char *s, int d, array<dword>& result_set);

partial_match_search позволяет находить множество слов из словаря удовлетворяющим шаблону.
например их словаря:

"one" "twa" "ane" "ono" "twas"

partial_match_search("?n?") найдет "one" "ane" "ono".

neighbour_search позволяет находить "похожие" словаю. Мера похожести задается параметром d — HAMMING DISTANCE [3].

например neighbour_search("twa",2) найдет два слова "twa" и "twas"

Замечания по имплементации:
1) Я использую свой array который может быть легко заменен на std::vector
2) Выбранный способ аллокации nodes (элементы в масиве) помимо всего прочего позволяет
задавать compiled static node tables — т.е. если у вас есть статическая таблица keywords то в принципе её можно скомпилировать и разместить в коде как static. Т.е. для проведения search не надо будет делать inserts при инициализации.

Алгоритм известен своей практически идеальной производительностью.
Во всяком случае теоретически лучше чем hash_table's

[1]слово — здесь есть конечная последовательность символов заканчивающаяся нулем)
[2]Теория ternary tree: http://home.od.ua/~relayer/algo/data/tern/lead.htm
[3]HAMMING DISTANCE: http://pespmc1.vub.ac.be/ASC/HAMMIN_DISTA.html

-------------------------------------------
source code:

namespace tool 
{
  template <typename CHAR>
    class ternary_tree
  {
    typedef unsigned int node_index;

  public:
    enum constants 
    {
        any_one_char = '?'
    };

    ternary_tree(): max_no(0) {}

    // 
    // returns number [1..max uint] of inserted or existing item.
    // does no insertion if item already exists. 
    //
    dword insert(const CHAR *s)
    {
      return (dword)nodes[insert(0, s)].eqkid;
    }

    // returns n[1..max_no] or zero if not found
    dword search(const CHAR *s) const
    {   
      node_index nid = 0; // root index;
      while (nid < total_nodes()) 
      {
         const node& n = nodes[nid];
         if (*s < n.splitchar)
             nid = n.lokid;
         else if(*s > n.splitchar)
             nid = n.hikid;
         else //(*s == p->splitchar) 
         {
            if (*s++ == 0)
                return n.value();
            nid = n.eqkid;
         } 
      }
      return 0;
    }
    // partial match search
    // e.g. 
    size_t partial_match_search(const CHAR *s, array<dword>& result_set ) const
    {
      partial_match_search(0,s,result_set);
      return result_set.size();
    }

    //
    // neighbour search 
    //
    // 'd' is Hamming distance of a query word: 
    //      A measure of the difference between two strings, 
    //      expressed by the number of characters that need to be changed to 
    //      obtain one from the other. 
    //      E.g., 0101 and 0110 has a Hamming distance of two 
    //      whereas "Butter" and "ladder" are four characters apart.
    //
    size_t neighbour_search(const CHAR *s, int d, array<dword>& result_set) const
    {
      neighbour_search(0, s, result_set, d);
      return result_set.size();
    }

 protected:
    typedef unsigned int node_index;
    
    struct node 
    {
       CHAR       splitchar;
       node_index lokid, eqkid, hikid;
       node():splitchar(0), lokid(-1), eqkid(-1), hikid(-1){}
       dword value() const 
       {
         assert(splitchar == 0);
         return (dword) eqkid;
       }
       void value(dword v)  
       {
         assert(splitchar == 0);
         eqkid = (node_index)v;
       }
    };

    array<node> nodes;
    dword       max_no;

    size_t      total_nodes() const { return (dword) nodes.size(); }
    
    node_index  insert(node_index nid, const CHAR *s)
    { 
       if (nid >= total_nodes()) 
       {
            node n; n.splitchar = *s;
            nodes.push(n);
            nid = nodes.last_index(); 
       }
       const node& n = nodes[nid];
       if (*s < n.splitchar)
          nodes[nid].lokid = insert(n.lokid, s);
       else if(*s > n.splitchar)
          nodes[nid].hikid = insert(n.hikid, s);
       else //*s == p->splitchar 
       {
          if (*s == 0)
          //"...we'll exploit the fact that a node with a 
          // null splitchar cannot have an eqkid, 
          // and store the data in that field."
              nodes[nid].value(++max_no);
          else
              nodes[nid].eqkid = insert(n.eqkid, ++s);
       }
       return nid;
    }

    //partial match search
    void partial_match_search(node_index nid, const CHAR *s, array<dword>& result_set ) const 
    {    
         if (nid >= total_nodes()) 
           return;
         const node& n = nodes[nid];
         if (*s == any_one_char || *s < n.splitchar)
            partial_match_search(n.lokid, s, result_set);
         if (*s == any_one_char || *s == n.splitchar)
            if (n.splitchar && *s)
                partial_match_search(n.eqkid, s+1, result_set);
         if (*s == 0 && n.splitchar == 0)
                result_set.push( (dword) n.value());
         if (*s == any_one_char || *s > n.splitchar)
                partial_match_search(n.hikid, s, result_set);
    }

    static int  length(const CHAR* s)
    {
      const CHAR* ps = s; while(*s) ++s; return s - ps;
    }

    void neighbour_search(node_index nid, const CHAR *s, array<dword>& result_set, int d) const
    {   
        if (nid >= total_nodes() || d < 0) return;

        const node& n = nodes[nid];      

        if (d > 0 || *s < n.splitchar)
            neighbour_search(n.lokid, s, result_set, d);
        if (n.splitchar == 0) 
        {
           if ( length(s) <= d)
              result_set.push(n.value());
        } 
        else
           neighbour_search(n.eqkid, *s ? s+1:s, result_set, (*s == n.splitchar) ? d:d-1 );
        if (d > 0 || *s > n.splitchar)
           neighbour_search(n.hikid, s, result_set, d);
    }


  };

}

Здравствуйте, c-smile, Вы писали:

CS>Второй вариант — воспользоваться предлагаемой имплементацией ternary tree [2]:

спасибо, очень полезная вещь.
правда я пока не тестил, но думаю от вас всё идёт со знаком качества.

кстати имплементацию в boost::spirit'е не смотрели?
если интересно то путь такой boost\spirit\symbols\impl\tst.ipp

Здравствуйте, korzhik, Вы писали:

K>Здравствуйте, c-smile, Вы писали:

CS>>Второй вариант — воспользоваться предлагаемой имплементацией ternary tree [2]:

K>спасибо, очень полезная вещь.
K>правда я пока не тестил, но думаю от вас всё идёт со знаком качества.

Спасибо

K>кстати имплементацию в boost::spirit'е не смотрели?
K>если интересно то путь такой boost\spirit\symbols\impl\tst.ipp

Спасибо за ссылку, глянул.

На вскидку что бросается в глаза сразу — это аллокция nodes в heap что в общем-то не эффективно для массива структур имеющих одинаковый размер экземпляров. Плюс расход памяти.
У меня например вместо указателя на node хранится его индекс который в большинстве случав может быть short int а не pointer как в boost/spirit.

Например для моего тестового примера таблица имен цветов в HTML (http://www.w3schools.com/html/html_colornames.asp) примерно 140 элементов.
Количество nodes примерно 1030. (Для справки общее количество символов во всех словах таблицы около 1200).Т.е. при аллокации на хипе несколько затратно/неэффективно получается.

Здравствуйте, c-smile, Вы писали:

[]

А что за array<> такой?

ME>А что за array<> такой?
возьму на себя смелость предположить, что из c-smile

Здравствуйте, MaximE, Вы писали:

ME>А что за array<> такой?

c-smile

src/tool/cs_array.h

Здравствуйте, korzhik, Вы писали:

K>Здравствуйте, MaximE, Вы писали:

ME>>А что за array<> такой?

K>c-smile

K>src/tool/cs_array.h

ну или так:

Замечания по имплементации:
1) Я использую свой array который может быть легко заменен на std::vector

Здравствуйте, c-smile, Вы писали:

CS>Допустим у нас есть некая таблица(а.к.а. словарь) состоящая из N ключевых слов[1].
CS>Нам нужно написать функцию типа:
CS>

CS>  int search(const char* some_word);
CS>

CS>которая быстро возвращает либо число из диапазона [1..N] если some_word в таблице или 0 если такого слова там нет.

У меня честно говоря не было времени вникать в сорсы и теорию, можно ли воспроизвести слово "быстро" в математических терминах типа О(х)?
И второй вопрос: может ли такое случиться, что при определенном наборе слов тернарное дерево вырождается, и какие действия предлагаются в этом случае для его балансировки?

Здравствуйте, Sergeem, Вы писали:

CS>>которая быстро возвращает либо число из диапазона [1..N] если some_word в таблице или 0 если такого слова там нет.

S>У меня честно говоря не было времени вникать в сорсы и теорию, можно ли воспроизвести слово "быстро" в математических терминах типа О(х)?
Насколько я понимаю поиск строки длины k в дереве с n элементами займет O(log n+k) шагов в худшем случае.

Здравствуйте, MaximE, Вы писали:

ME>А что за array<> такой?

Примерно вот это
http://www.rsdn.ru/Forum/?mid=724485
Код этого array уже давно устарел (например сейчас сделана оптимизация под POD типы).
Здесь же приводится в качестве примера начальный вариант.

Здравствуйте, Sergeem, Вы писали:

S>У меня честно говоря не было времени вникать в сорсы и теорию, можно ли воспроизвести слово "быстро" в математических терминах типа О(х)?
S>И второй вопрос: может ли такое случиться, что при определенном наборе слов тернарное дерево вырождается, и какие действия предлагаются в этом случае для его балансировки?

Time Complexity

In a balanced ternary search tree with n nodes where all the keywords
of the nodes are k characters long, we want to search a k character long input string. The total number of character-to-character comparisons is at most

lg n + k.

For a balanced binary search tree of n-nodes and k character long keywords, the total number of character-to-character comparisons is at most

k * lg n

which is substantially larger than lg n + k for large n.

Ternary tree не требует балансировки.
Оно всегда в "хорошем состянии"

In what order should you insert the nodes into a tree? No matter in what order you insert the nodes, you end up with the same digital search trie -- the data structure is totally insensitive to insertion order.
Binary search trees are at the opposite end of the spectrum: If you insert the nodes in a good order (middle element first), you end up with a balanced tree. If you insert the nodes in sorted order, the result is a long skinny tree that is very costly to build and search. Fortunately, if you insert the nodes in random order, a binary search tree is usually close to balanced.

Тем не менее скорость работы функции insert зависит от порядка следования подаваемых слов, search — нет.

Справедливости ради надо отметить что hash-table как механизм тоже вельми эффеткивен.
При хорошем раскладе (а.к.а. неловленный мизер) количество character-to-character comparisons
может быть вообще

2 * k

(я приравниваю сложность обработки одного символа при вычислении хэш функции к одному сравнению, что в общем не так, но близко).

При плохом раскладе (все слова попали в один collision chain) количество сравнений

(n+1) * k

что маловероятно но может случится.

Примерно так.

Здравствуйте, c-smile, Вы писали:

CS>Ternary tree не требует балансировки.
CS>Оно всегда в "хорошем состянии"

Скорее всего это было мое оптимистичное заявление.

Потому как вот:

The input order of data cells into a ternary search trie is still important to create balanced tree, but less important than in a binary search tree.
According to many authors ([Mehlhorn79] and [Bentley and Saxe79]), by choosing the true median of a set of data-cells as the starting node, we can create a well-balanced ternary tree without the randomizing proces

http://www.cs.caltech.edu/~shang/project/report.doc

Здравствуйте, c-smile, Вы писали:

CS>Здравствуйте, c-smile, Вы писали:

CS>>Ternary tree не требует балансировки.
CS>>Оно всегда в "хорошем состянии"

CS>Скорее всего это было мое оптимистичное заявление.

CS>Потому как вот:
CS>

CS>The input order of data cells into a ternary search trie is still important to create balanced tree, but less important than in a binary search tree.
CS>According to many authors ([Mehlhorn79] and [Bentley and Saxe79]), by choosing the true median of a set of data-cells as the starting node, we can create a well-balanced ternary tree without the randomizing proces

CS>http://www.cs.caltech.edu/~shang/project/report.doc

Написание сбалансированного третичного дерева оставим студентам в качестве домашнего задания

Здравствуйте, Sergeem, Вы писали:

S>Здравствуйте, c-smile, Вы писали:

CS>>Допустим у нас есть некая таблица(а.к.а. словарь) состоящая из N ключевых слов[1].
CS>>Нам нужно написать функцию типа:
CS>>

CS>>  int search(const char* some_word);
CS>>

CS>>которая быстро возвращает либо число из диапазона [1..N] если some_word в таблице или 0 если такого слова там нет.

S>У меня честно говоря не было времени вникать в сорсы и теорию, можно ли воспроизвести слово "быстро" в математических терминах типа О(х)?
S>И второй вопрос: может ли такое случиться, что при определенном наборе слов тернарное дерево вырождается, и какие действия предлагаются в этом случае для его балансировки?

По многим вопросам, и в частности по вопросу тернарного дерева(кстати, на днях сам реализовывал, поздно заглянул сюда), ИМХО, лучше обратиться к Седжвику. Там все достаточно подробно и авторитетно расписано, в том числе есть ответы и на ваши вопросы.

... << RSDN@Home 1.1.4 @@subversion >>

Здравствуйте, c-smile, Вы писали:

CS>Класс ternary_tree кроме двух очевидных и полезных методов:

CS>

CS>dword ternary_tree::insert(const char* s);
CS>dword ternary_tree::search(const char* s);
CS>

Тестировал функцию insert она всегда возвращает 1.
Это так и задумывалось?

Здравствуйте, Dmitry521, Вы писали:

CS>>

CS>>dword ternary_tree::insert(const char* s);
CS>>dword ternary_tree::search(const char* s);
CS>>

D>Тестировал функцию insert она всегда возвращает 1.
D>Это так и задумывалось?

Да.

Потому как 0 возвращаемый dword search(const char* s)
означает — такого слова нет.

CS>  int search(const char* some_word);
CS>

CS>которая быстро возвращает либо число из диапазона [1..N] если some_word в таблице или 0 если такого слова там нет.

CS>Задача построения такой функции решаема несколькими вариантами, один из них например
CS>построить т.н. minimal perfect hash function с помощью например gperf (но это возможно не на каждом наборе).
[skiped]
CS>

Решил испытать ваше решение,
После объявления
tool::ternary_tree<char> TST;
при попытке компиляции вываливается:

d:\Prog. NET\Solution1\Dict_Search\main.cpp(230) : error C2440: '=' : cannot convert from 'const tool::ternary_tree<CHAR>::node' to 'tool::ternary_tree<CHAR>::node_index'

 node_index  insert(node_index nid, const CHAR *s)
    { 
       if (nid >= total_nodes()) 
       {
            node n; n.splitchar = *s;
            nodes.push(n);
            nid = nodes.last_index();        // здесь ошибка
         }

Может быть подскажете, что не так делаю?
И еще вопрос параллелльно : на сколько ваш array по быстродействию выигрывает у vector? Думаю, измерения проводились...

... << RSDN@Home 1.1.4 @@subversion >>

Здравствуйте, Dr.Gigabit, Вы писали:

Вот тот же код, слегка переделанный под std::vector, вроде работает.

#include <vector>

typedef unsigned int dword;

namespace tool 
{
  template <typename CHAR>
    class ternary_tree
  {
    typedef unsigned int node_index;

  public:
    enum constants 
    {
        any_one_char = '?'
    };

    ternary_tree(): max_no(0) {}

    // 
    // returns number [1..max uint] of inserted or existing item.
    // does no insertion if item already exists. 
    //
    dword insert(const CHAR *s)
    {
      return (dword)nodes[insert(0, s)].eqkid;
    }

    // returns n[1..max_no] or zero if not found
    dword search(const CHAR *s) const
    {   
      node_index nid = 0; // root index;
      while (nid < total_nodes()) 
      {
         const node& n = nodes[nid];
         if (*s < n.splitchar)
             nid = n.lokid;
         else if(*s > n.splitchar)
             nid = n.hikid;
         else //(*s == p->splitchar) 
         {
            if (*s++ == 0)
                return n.value();
            nid = n.eqkid;
         } 
      }
      return 0;
    }
    // partial match search
    // e.g. 
    size_t partial_match_search(const CHAR *s, std::vector<dword>& result_set ) const
    {
      partial_match_search(0,s,result_set);
      return result_set.size();
    }

    //
    // neighbour search 
    //
    // 'd' is Hamming distance of a query word: 
    //      A measure of the difference between two strings, 
    //      expressed by the number of characters that need to be changed to 
    //      obtain one from the other. 
    //      E.g., 0101 and 0110 has a Hamming distance of two 
    //      whereas "Butter" and "ladder" are four characters apart.
    //
    size_t neighbour_search(const CHAR *s, int d, std::vector<dword>& result_set) const
    {
      neighbour_search(0, s, result_set, d);
      return result_set.size();
    }

 protected:
    typedef unsigned int node_index;
    
    struct node 
    {
       CHAR       splitchar;
       node_index lokid, eqkid, hikid;
       node():splitchar(0), lokid(-1), eqkid(-1), hikid(-1){}
       dword value() const 
       {
         //assert(splitchar == 0);
         return (dword) eqkid;
       }
       void value(dword v)  
       {
         //assert(splitchar == 0);
         eqkid = (node_index)v;
       }
    };

    std::vector<node> nodes;
    dword       max_no;

    size_t      total_nodes() const { return (dword) nodes.size(); }
    
    node_index  insert(node_index nid, const CHAR *s)
    { 
       if (nid >= total_nodes()) 
       {
            node n; n.splitchar = *s;
            nodes.push_back(n);
            nid = nodes.size() - 1; 
       }
       const node& n = nodes[nid];
       if (*s < n.splitchar)
          nodes[nid].lokid = insert(n.lokid, s);
       else if(*s > n.splitchar)
          nodes[nid].hikid = insert(n.hikid, s);
       else //*s == p->splitchar 
       {
          if (*s == 0)
          //"...we'll exploit the fact that a node with a 
          // null splitchar cannot have an eqkid, 
          // and store the data in that field."
              nodes[nid].value(++max_no);
          else
              nodes[nid].eqkid = insert(n.eqkid, ++s);
       }
       return nid;
    }

    //partial match search
    void partial_match_search(node_index nid, const CHAR *s, std::vector<dword>& result_set ) const 
    {    
         if (nid >= total_nodes()) 
           return;
         const node& n = nodes[nid];
         if (*s == any_one_char || *s < n.splitchar)
            partial_match_search(n.lokid, s, result_set);
         if (*s == any_one_char || *s == n.splitchar)
            if (n.splitchar && *s)
                partial_match_search(n.eqkid, s+1, result_set);
         if (*s == 0 && n.splitchar == 0)
                result_set.push_back( (dword) n.value());
         if (*s == any_one_char || *s > n.splitchar)
                partial_match_search(n.hikid, s, result_set);
    }

    static int  length(const CHAR* s)
    {
      const CHAR* ps = s; while(*s) ++s; return s - ps;
    }

    void neighbour_search(node_index nid, const CHAR *s, std::vector<dword>& result_set, int d) const
    {   
        if (nid >= total_nodes() || d < 0) return;

        const node& n = nodes[nid];      

        if (d > 0 || *s < n.splitchar)
            neighbour_search(n.lokid, s, result_set, d);
        if (n.splitchar == 0) 
        {
           if ( length(s) <= d)
              result_set.push_back(n.value());
        } 
        else
           neighbour_search(n.eqkid, *s ? s+1:s, result_set, (*s == n.splitchar) ? d:d-1 );
        if (d > 0 || *s > n.splitchar)
           neighbour_search(n.hikid, s, result_set, d);
    }


  };

}

От:	c-smile	http://terrainformatica.com
Дата:	24.09.04 20:25
Оценка:	156 (19)

	От:	korzhik
	Дата:	24.09.04 20:53
	Оценка:	+1

От:	c-smile	http://terrainformatica.com
Дата:	24.09.04 21:25
Оценка:

	От:	MaximE
	Дата:	27.09.04 08:33
	Оценка:

От:	Dmitry A. Sinyagin	www.astawireless.com
Дата:	27.09.04 09:56
Оценка:

	От:	Dr.Gigabit
	Дата:	28.09.04 21:41
	Оценка:

	От:	Dmitry521
	Дата:	14.10.04 13:12
	Оценка:

	От:	Dr.Gigabit
	Дата:	17.10.04 20:32
	Оценка:

	От:	Dmitry521
	Дата:	18.10.04 08:23
	Оценка: