• std::map — 39.1 сек.
  
• pat_map — 29.0 сек.

__>Ждем

• все интерфейсные функции и классы помещены в namespace pat, особенности реализации — в pat::impl;
  
• добавлен функтор-Decision HammingDistance, выполняющий функции отбора ключей, дистанция Хемминга которых в сравнении с образцом не более заданной величины (см. здесь
  Автор: c-smile
  Дата: 25.09.04
  ), пример — в patcont.cpp;
  
• в классы partimator'ов добавлены методы для реализации обхода дерева в ширину (см. функтор FixedLength в partial.h, в принципе можно комбинировать и остальные функторы):
  — bool leaf() — true, если партиматор указывает на лист;
  — [const_][reverse_]iterator|partimator [r]begin|end([const Decis2&]) — для получения вложенного итератора|партиматора.
  Пример работы см. build_re.cpp (аналогично этому
  Автор: sergey_shandar
  Дата: 13.04.04
  );
  
• пофиксены некоторые редчайшие баги.

• хотелось бы доделать erase, однако это не так уж тривиально;
  
• есть мысли реализовать контейнеры, аналогичные суффиксным деревьям (время добавления очередного суффикса константно) на уже имеющейся основе, но это уже довольно значительный уход от парадигмы стандартных контейнеров STL и неслабая возня с шаблонами;
  
• [почти] нереальные фантазии о не-бинарных деревьях цифрового поиска PATRICIA.

__>Было бы неплохо сделать более полный тест скорости работы класса.

• проект переведён с лицензии GPL на Boost Software License, как более приемлемой для библиотечного шаблонного кода;
  
• код полностью пересмотрен и кое-где исправлен;
  
• в наиболее интересных местах добавлены комментарии;
  
• bit_comparator'ы теперь реализованы в виде функторов (для большей гибкости и схожести с предикатами STL);
  
• реализованы все конструкторы, полагающиеся ассоциативным контейнерам STL, шаблон метода insert range и методы bit_comp (аналог key_comp) и get_allocator;
  
• метод optimize, реинициализирующий внутренний вектор shortcut, для более эффективного поиска/вставки. Также, после каждой вставки, optimize вызывается автоматически по эмпирическому условию;
  
• полностью реализованы partimator'ы: все возможные шаблоны итераторов частичного совпадения и шаблоны методов [r]begin, [r]end для них. Пример работы — см. patcont.cpp;
  
• появилась возможность указывать, какого размера будет shortcut, при специализации контейнера, что позволяет гибче управлять соотношением производительность/память:

  trie_map<std::string,unsigned,bit_comparator<std::string,16> > map16;
  // sizeof(map16.shortcut) == (1<<16)*sizeof(unsigned)
  trie_map<std::string,unsigned> map0;
  // sizeof(map0.shortcut) == (1<<0)*sizeof(unsigned) // по умолч. длина префикса =0

• lower_bound, upper_bound, equal_range и count получили второй параметр со значением по умолчанию (длина префикса в битах);
  
• insert с параметром hint (подсказка для вставки за O(1)) выкинут за ненадобностью;
  
• введёны новые типы итераторов — partial match iterators (partimators ) — const_partimator, partimator. Позволяют обходить дерево не полностью, заходя только в нужные поддеревья и проверяя совпадение с маской (как здесь
  Автор: c-smile
  Дата: 25.09.04
  );
  
• бит-компараторы для следующих типов ключей: standard finite std::string (тестировался только этот), simple infinite (char*) string, finite (char*) string with ASCIIZ semantics;
  
• внутренний вектор shortcut — для константного доступа к узлу при поиске/вставке для префикса заранее заданной длины;
  
• в качестве примера эмуляции хеш-таблицы (см. здесь
  Автор: cranky
  Дата: 04.09.05
  ) реализован специальный класс DelusionString с соответствующим bit_comparator (см. bit_comp.h);

• trie_set и trie_map
  
• вынос интерфейса bit_comparator из ключа
  
• поддержка стандартных allocator'ов
  
• реализация всех методов ассоциативных контейнеров (кроме некоторых конструкторов и erase)
  
• слегка увеличена скорость

RK>>MSVC 7.1 (w/o PAT_SHORTCUTS) File: 93 М (russian words)

RK>>*** pat::trie_set
RK>>Timer: 37.3867 sec.
RK>>Size: 404463
RK>>Timer erase: 0.297726 sec.
RK>>*** std::set
RK>>Timer: 54.5871 sec.
RK>>Size: 404463
RK>>Timer erase: 0.302945 sec.
RK>>*** std::hash_set
RK>>Timer: 28.5497 sec.
RK>>Size: 404463
RK>>*** std::hash_set: to std::vector + std::sort
RK>>Timer: 1.42755 sec.
RK>>Size: 404463
RK>>Full hash timer: 29.9773 sec.


RK>>GCC 3.4.4 (w/o PAT_SHORTCUTS) File: 93 М (russian words)

RK>>*** pat::trie_set
RK>>Timer: 27.9667 sec.
RK>>Size: 404463
RK>>Timer erase: 0.476102 sec.
RK>>*** std::set
RK>>Timer: 45.1105 sec.
RK>>Size: 404463
RK>>Timer erase: 0.482932 sec.
RK>>*** std::hash_set
RK>>Timer: 16.078 sec.
RK>>Size: 404463
RK>>*** std::hash_set: to std::vector + std::sort
RK>>Timer: 1.94486 sec.
RK>>Size: 404463
RK>>Full hash timer: 18.0229 sec.
RK>>
__>

MSVC 7.1 (PAT_SHORTCUTS) File: 93 М (russian words)

*** pat::trie_set
Timer: 34.4867 sec.
Size: 404463
*** pat::trie_set<pat::DelusionString>
Timer: 29.6441 sec.
Size: 404463


GCC 3.4.4 (PAT_SHORTCUTS) File: 93 М (russian words)

*** pat::trie_set
Timer: 25.2501 sec.
Size: 404463
*** pat::trie_set<pat::DelusionString>
Timer: 23.0039 sec.
Size: 404463

pat::trie_map<std::string,unsigned,pat::reverse_bit_comparator<std::string> >

class string_hash_compare
    : public hash_compare<string>
{
public:
    size_t operator()(const string &key) const
    {
        size_t h=0;
        for (string::const_iterator it=key.begin();it!=key.end();++it)
            h=5*h+*it;
        return h;
    }
    bool operator()(const string &key1,const string &key2) const
    {
        return comp(key1,key2);
    }
};

В большинстве реализаций STL существуют два подхода для организации отображений: map и hash_map. Ни тот, ни другой не являются эффективными для не-скалярных типов, таких как массивы, строки и т.п.

    size_t operator()(const string &key) const
    {
        size_t h=0,g;
        for (string::const_iterator it=key.begin();it!=key.end();++it)
        {
            if (g=(h=(h<<4)+*it)&0xF0000000)
                h^=g>>24^g;
        }
        return h;
    }

• trie_set и trie_map
  
• вынос интерфейса bit_comparator из ключа
  
• поддержка стандартных allocator'ов
  
• реализация всех методов ассоциативных контейнеров (кроме некоторых конструкторов и erase)
  
• слегка увеличена скорость

• lower_bound, upper_bound, equal_range и count получили второй параметр со значением по умолчанию (длина префикса в битах). Теперь можно получить итераторы границ интервала, содержащего все ключи с заданным префиксом. Пример см. в patcont.cpp;
  
• insert с параметром hint (подсказка для вставки за O(1)) выкинут за ненадобностью;
  
• введёны новые типы итераторов — partial match iterators (partimap ) — const_partimap, partimap. Позволяют обходить дерево не полностью, заходя только в нужные поддеревья. Шаблоны классов этих итераторов параметризуются типом Decision — функтором, определяющим надо ли заходить в указанное поддерево. Пример реализации класса Decision имеется в partial.h, PartialMatch, и реализует прохождение дерева для поиска всех частичных совпадений по ключу (как здесь
  Автор: c-smile
  Дата: 25.09.04
  ). В дальнейшем планируются const_reverse_partimap, reverse_partimap, а также другие реализации интерфейса Decision для разных задач поиска совпадений;
  
• бит-компараторы для следующих типов ключей: standard finite std::basic_string<char> (тестировался только этот), simple infinite (char*) string, finite (char*) string with ASCIIZ semantics;
  
• внутренний вектор shortcut — для константного доступа к узлу при поиске/вставке для префикса заранее заданной длины (в моей реализации бит-компараторов — 16 бит (см. bit_comp.h));
  
• в качестве примера эмуляции хеш-таблицы (см. здесь
  Автор: cranky
  Дата: 04.09.05
  ) реализован специальный класс DelusionString с соответствующим bit_comparator (bit_comp.h), кеширующий 16 младших бит хеш-значения для строки. Для сборки в режиме эмуляции хеш-таблицы следует раскомментировать #define PAT_DELUSION в patcont.cpp. После запуска получается неотсортированный по ключу результат, но зато даже немного быстрее, чем используя hash_map с той же хеш-функцией. В таком варианте контейнеры trie_map и trie_set теряют все свои возможности, связанные с последовательной выборкой битов из ключа;
  
• возможно что-то ещё забыл

• trie_set и trie_map
  
• вынос интерфейса bit_comparator из ключа
  
• поддержка стандартных allocator'ов
  
• реализация всех методов ассоциативных контейнеров (кроме некоторых конструкторов и erase)
  
• слегка увеличена скорость

• Добил-таки erase(iterator), впрочем, и он меня тоже, но об этом потом. Ирейз получился красивый, константный и жутко быстрый. Зацените код:
  

  void erase(iterator delIt)
  {
      // retrieve Algorithm structure from iterator
      Algorithm pal(delIt);
      // q back-point to p, p & q may point to same node
      Node *q=pal.getQ(),*p=pal.getP();
      // pBrother - sibling of p
      const unsigned
          pBrotherId=1ul^pal.getQid(),
          pBrotherTag=q->getXtag(pBrotherId);
      Node *pBrother=q->getXlink(pBrotherId);
      // take parent of q
      const unsigned qParentId=q->getParentId();
      Node *qParent=q->getParent();
      // if parent of q exist
      if (qParent)
      {
          // replace q with p-brother
          qParent->setXlinktag(qParentId,pBrother,pBrotherTag);
          if (!pBrotherTag)
              pBrother->setParentid(qParent,qParentId);
      }
      // if p & q isn't equal
      if (q!=p)
      {
          // make q identical to p
          q->setAllButValue(*p);
          Node *pParent=p->getParent();
          // correct parent of p if exist
          if (pParent)
              pParent->setXlinktag(p->getParentId(),q,0);
          // correct childs of p
          for (unsigned i=0;i!=2;++i)
          {
              if (!p->getXtag(i))
                  p->getXlink(i)->setParentid(q,i);
          }
      }
      // special case: del root
      if (p==root_)
          root_=q==p?0:q;
      // sic transit gloria mundi
      delNode(p);
      // decrease size
      --size_;
  #ifdef PAT_SHORTCUTS
      // fix shortcuts
      optimize();
  #endif
  }

  
  Как вы уже, наверное, заметили, метод возвращает void, хотя стандартный должен вернуть iterator на следующий после удаляемого элемент. Но увы, эффективно найти этот итератор не позволяет сама природа PATRICIA trie: каждый узел является одновременно и веткой и листом. Таким образом, на каждое хранимое значение существуют два указателя: как на поддерево (обычный указатель на детей) и как на лист (обратная ссылка, в Кнуте обозначается штриховой стрелкой). Благодаря этому, кстати, и становятся возможными partimator'ы с заходом только в нужные поддеревья.
  Подумав, как можно было бы исправить ситуацию, я понял, что trie не сможет обеспечить валидность итераторов после удаления узла. Ещё через пару минут сообразил, что итераторы инвалидируются также после вставки узла. Получается, что условия по сохранности итераторов, которые обеспечивают стандартные ассоциативные контейнеры (итератор на элемент контейнера живёт пока жив элемент под итератором), нельзя выполнить для контейнеров, основанных на PATRICIA trie. Единственное исключение — итераторы, возвращаемые end() и rbegin() — их правильность распространяется на всё время жизни контейнера. Также после вставки/удаления не сохраняются партиматоры, но для них нет никаких гарантий даже для end() и rbegin(). Вот так, немного грустно, но суббота была непоправимо испорчена с полдня.
  Неизбежные следствия: невозможно эффективно реализовать erase(iterator first,iterator last), нельзя просто пробежаться по контейнеру и удалить ненужные элементы, придётся начинать или с begin() или с end() после каждого удаления. Впрочем, я ещё попробую подумать над вычислением в erase() следующего итератора: тут не всё так запущено, я думаю...
  Ещё, чуть не забыл: в связи с тем, что при удалении обновляются несколько разных узлов, необходимо пересчитывать вектор shortcut (методом optimize()), что требует немало времени (для 16-битных префиксов нужно обновить 2^16 элементов). По тестам выходит, что скорость удаления в этом случае понижается в ~20 раз. Поэтому в будущем лучше отказаться от этой небольшой (8-10%) оптимизации, тем более, что в одной из следующих версий, надеюсь, образуются не-бинарные деревья — и шоткаты станут совсем ненужны.
  
• В качестве бонуса к erase() набросал небольшой адаптер unique_priority_queue для trie_set и set. Функциональность у него ровно такая же, как и у std::priority_queue (основанного на хипе), но сохраняются только уникальные значения. Естественно, для не-скалярных типов у trie_set наблюдается преимущество в производительности push/pop, по сравнению с std::set (см. результаты теста дальше).
  
• Новые бит-компараторы: для unsigned и int. Вдруг кому пригодятся?

__>>>Было бы неплохо сделать более полный тест скорости работы класса.

__>Между компиляторами и с std::map/std::set

MSVC 7.1 (PAT_SHORTCUTS) File: 93 М (russian words)

*** pat::trie_set
Timer: 34.4867 sec.
Size: 404463
*** pat::trie_set<pat::DelusionString>
Timer: 29.6441 sec.
Size: 404463


MSVC 7.1 (w/o PAT_SHORTCUTS) File: 93 М (russian words)

*** pat::trie_set
Timer: 37.3867 sec.
Size: 404463
Timer erase: 0.297726 sec.
*** std::set
Timer: 54.5871 sec.
Size: 404463
Timer erase: 0.302945 sec.
*** std::hash_set
Timer: 28.5497 sec.
Size: 404463
*** std::hash_set: to std::vector + std::sort
Timer: 1.42755 sec.
Size: 404463
Full hash timer: 29.9773 sec.


GCC 3.4.4 (PAT_SHORTCUTS) File: 93 М (russian words)

*** pat::trie_set
Timer: 25.2501 sec.
Size: 404463
*** pat::trie_set<pat::DelusionString>
Timer: 23.0039 sec.
Size: 404463


GCC 3.4.4 (w/o PAT_SHORTCUTS) File: 93 М (russian words)

*** pat::trie_set
Timer: 27.9667 sec.
Size: 404463
Timer erase: 0.476102 sec.
*** std::set
Timer: 45.1105 sec.
Size: 404463
Timer erase: 0.482932 sec.
*** std::hash_set
Timer: 16.078 sec.
Size: 404463
*** std::hash_set: to std::vector + std::sort
Timer: 1.94486 sec.
Size: 404463
Full hash timer: 18.0229 sec.



---------------- [unique_]priority_queue


MSVC 7.1 File: 93 М (russian words)

*** std::priority_queue
Timer: 66.5425 sec.
*** pat::unique_priority_queue
Timer: 31.2714 sec.
*** pat::unique_priority_queue<std::set>
Timer: 43.163 sec.


GCC 3.4.4 File: 93 М (russian words)

*** std::priority_queue
Timer: 88.7093 sec.
*** pat::unique_priority_queue
Timer: 31.46 sec.
*** pat::unique_priority_queue<std::set>
Timer: 42.5287 sec.

__>Кстати версия 0.19 не компилируется с STLPort, так как в нем нет hash_compare.

--------------- STLPort


MSVC 7.1 + STLPort 4.6.2 (PAT_SHORTCUTS) File: 93 М (russian words)

*** pat::trie_set
Timer: 20.7815 sec.
Size: 404463
Timer erase: 10.9516 sec.
*** pat::trie_set<pat::DelusionString>
Timer: 19.1018 sec.
Size: 404463
*** std::set


MSVC 7.1 + STLPort 4.6.2 (w/o PAT_SHORTCUTS) File: 93 М (russian words)

*** pat::trie_set
Timer: 21.983 sec.
Size: 404463
Timer erase: 0.156297 sec.
*** std::set
Timer: 53.3017 sec.
Size: 404463
Timer erase: 0.140155 sec.
*** std::hash_set
Timer: 10.9704 sec. // поражает воображение!
Size: 404463
*** std::hash_set: to std::vector + std::sort
Timer: 1.44805 sec.
Size: 404463
Full hash timer: 12.4185 sec.

inline size_t __stl_hash_string(const char* __s)
{
  _STLP_FIX_LITERAL_BUG(__s)
  unsigned long __h = 0; 
  for ( ; *__s; ++__s)
    __h = 5*__h + *__s;
  
  return size_t(__h);
}

• Добавлен метод:

  size_type erase(const key_type &key,unsigned prefixLen=~0ul)

  для удаления сразу всех значений, ключи которых начинаются с заданного префикса. Работает быстро: сначала находит поддерево с заданным префиксом за логарифмическое время, затем вырезает это поддерево из основного дерева за константное время и, наконец, рекурсивно освобождает память, выделенную под узлы в данном поддереве. Если prefixLen задан по умолчанию ~0ul, вырезается максимум один узел с заданным ключом, т.е. поведение в этом случае стандартное. Метод возвращает кол-во удалённых значений.
  
• Эффективно получать следующий после удалённого итератор я так и не смог, но есть надежда сделать erase(iterator,iterator) через последовательное удаление узлов с одинаковым префиксом, пока не реализовано.

контейнеры, аналогичные суффиксным деревьям (время добавления очередного суффикса константно)

// constructor
suffix_set(
    key_type keys,            // передается указатель на начало суффиксного буфера (на первый суффикс)
    size_type size,            // размер окна (одновременно индексируемых суффиксов)
    const bit_compare &bitComp=bit_compare(),
    const allocator_type &alloc=allocator_type());
// в конструкторе сразу добавляется первый узел, он же root
// инвариант для suffix_set: в контейнере должен быть хотя бы один суффикс
    
// вставляем очередной суффикс (следующий по возрастанию адресов)
void push_back();

// удаляем наиболее ранний суффикс (первый по порядку добавления)
void pop_front(); // именно этот метод делает suffix_set динамическим

bool full() const; // true, если нет места для добавления очередного суффикса

size_type size() const; // возвращает текущее кол-во суффиксов

• Бит-компараторы теперь существуют для std::basic_string<T>, т.е. как минимум для std::string и std::wstring; также для любого указателя вида T*.
  
• Decision-функторы PartialMatch и HammingDistance теперь специализируются типом контейнера, отчего стало возможным применять их с любыми возможными бит-компараторами. При тестировании с суффиксными контейнерами была обнаружена и исправлена ошибка в механизме партиматоров, заодно избавился от довольно глубокой рекурсии. Сейчас в работе итераторов частичного совпадения есть только одно ограничение: функтор HammingDistance оказалось невозможным применять с реверсивными итераторами, потому что он содержит mutable-члены. В остальных случаях — это действительно работает! Проверено.
  
• В результате обобщения всех контейнеров образовался дополнительный внутренний класс impl::assoc_generic, в который вынесены все итераторы ([const_][reverse_](iterator|partimator)) и методы, общие для всех четырёх контейнеров: [r](begin|end), find, (lower_|upper_)bound, equal_range, count.
  
• Из прототипа suffix_set предыдущей версии образовались два новых шаблонных контейнера:
  

  template <
      typename Type,
      int delta=1, // расстояние в bitT между соседними суффиксами
      typename BitComp=bit_comparator<Type>,
      typename Allocator=std::allocator<Type> >
  class suffix_set;
  
  template <
      typename Type,
      typename Datum,
      int delta=1, // расстояние в bitT между соседними суффиксами
      typename BitComp=bit_comparator<Type>,
      typename Allocator=std::allocator<Type> >
  class suffix_map;

  
  Краткое описание всех методов этих шаблонов — в suffix_set.h. Недостаточно потестированные методы, возможны баги: pop_front, pop_back.
  
• Некоторые примеры использования суффиксных деревьев: линейный поиск множества ключей (multi_search.cpp) и преобразование BWT (или лексическая сортировка, сложность также линейная), см. usort3.cpp. Для сравнения приведёна версия 2.33 USORT, применяющая для сортировки обычное дерево PATRICIA (сложность приблизительно O(N*log N)).
  
• Обобщить suffix_map и suffix_set мне так и не удалось. Несмотря на практически полную идентичность интерфейса, контейнеры эти различаются в некоторых внутренних деталях. Также очень не нравится обилие protected-членов в промежуточных классах — есть подозрение, что можно сделать лучше. Если кто-нибудь сможет помочь исправить ситуацию, буду дико благодарен Готов пойти на любые издержки — вплоть до переписывания всего кода (нам не привыкать).
  
• Документацию решил сделать автоматически генерируемой doxygen'ом. Пока, только ради эксперимента, потренировался на algorithm.h. Опять же, замечания приветствуются.