Txでdartsのようなtraverseをする関数を作ってみました。

使い方はdartsのtraverseと同じだと思います。たまたま作ったのでパッチをそのまま貼っておきます。動作は未保証。dartsよりも爆速でふきました。

PLAIN TEXT
CODE:
  1. diff -cb tx-0.13/tx.cpp tx_original/tx.cpp
  2. *** tx-0.13/tx.cpp  2009-04-13 13:21:14.000000000 +0900
  3. --- tx_original/tx.cpp  2009-08-27 22:45:25.000000000 +0900
  4. ***************
  5. *** 195,200 ****
  6. --- 195,221 ----
  7.       return 0;
  8.     }
  9.    
  10. +   uint tx::traverse(const char* str, size_t& pos) const {
  11. +       uint curPos = 2;
  12. +       uint retId = NOTFOUND;
  13. +       size_t begin = pos;
  14. +       if (terminal.getSize() <= 2) return retId;
  15. +
  16. +       for (size_t i = 0 ; ; i++){
  17. +           const uint nodeId = loud.rank(curPos-1,1)-1;
  18. +           if (terminal.getBit(nodeId)){
  19. +               pos = begin + i;
  20. +               retId = terminal.rank(nodeId,1)-1;
  21. +           }
  22. +           uint nextPos = getChild(curPos,str[begin + i]);
  23. +           if (nextPos == UINT_MAX){
  24. +               break;
  25. +           }
  26. +           curPos = nextPos;
  27. +       }
  28. +       return retId;
  29. +   }
  30. +
  31.     uint tx::prefixSearch(const char* str, const size_t len, size_t& retLen) const {
  32.       uint curPos = 2;
  33.       uint retId = NOTFOUND;
  34. diff -cb tx-0.13/tx.hpp tx_original/tx.hpp
  35. *** tx-0.13/tx.hpp  2008-06-03 21:05:00.000000000 +0900
  36. --- tx_original/tx.hpp  2009-08-27 22:41:04.000000000 +0900
  37. ***************
  38. *** 26,31 ****
  39. --- 26,32 ----
  40.       int read(const char* fileName);
  41.  
  42.       uint prefixSearch(const char* str, const size_t len, size_t& retLen) const;
  43. +     uint traverse(const char* str, size_t& pos) const;
  44.       uint expandSearch(const char* str, const size_t len, std::vector<std::string>& ret, const uint limit = 0) const;
  45.       uint commonPrefixSearch(const char* str, const size_t len, std::vector<std::string>& ret, std::vector<uint>& retID,  const uint limit = TX_LIMIT_DEFAULT) const;
  46.       uint commonPrefixSearch(const char* str, const size_t len, std::vector<uint>& retLen, std::vector<uint>& retID,  const uint limit = TX_LIMIT_DEFAULT) const;
  47. ***************
  48. *** 42,48 ****
  49.      
  50.       static uint NOTFOUND;
  51.      
  52. !   private:
  53.       uint getChild(const uint pos, const char c) const;
  54.       uint getParent(const uint pos, char& c) const;
  55.       void enumerateAll(const uint pos, const std::string str, std::vector<std::pair<size_t, std::pair<std::string, uint>>>& ret) const;
  56. --- 43,49 ----
  57.      
  58.       static uint NOTFOUND;
  59.      
  60. ! //  private:
  61.       uint getChild(const uint pos, const char c) const;
  62.       uint getParent(const uint pos, char& c) const;
  63.       void enumerateAll(const uint pos, const std::string str, std::vector<std::pair<size_t, std::pair<std::string, uint>>>& ret) const;