進・日進月歩

IT, Jazz, study, engineering, すべての真実とクリエイティビティのために

Archive for August, 2009

Txでdartsのようなtraverseをする関数

  • Author: harajune
  • Filed under: 雑記
Monday
Aug 31,2009

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;

  • 1 Comment

    • sennaでpatricia treeを作る

    • Author: harajune
    • Filed under: IT
    Friday
    Aug 28,2009

    はてなのようなキーワードリンクをRubyで付与する実例
    と、いうのをつくってもらったので、これをもとにCでsennaのpatricia treeを試すプログラムを書いたよ。

    機能的にはとりあえずキーワードの検出だけ。

    PLAIN TEXT
    CODE:
    1. #include <stdio.h>
    2. #include <stdlib.h>
    3. #include <senna/senna.h>
    4. #include <string.h>
    5. //#include <exectime.h>
    6.  
    7. void create_index(char* index, char* filename){
    8.  
    9.         sen_sym *sym;
    10.  
    11.         if(!(sym = sen_sym_create(index, 0, SEN_INDEX_NORMALIZE, sen_enc_utf8))){
    12.             printf("cannot open or create sym file\m");
    13.             abort();
    14.         }
    15.  
    16.         FILE * fp = fopen(filename, "rb");
    17.  
    18.         char buffer[2048];
    19.        
    20.         sen_id sym_id;
    21.         while(fgets(buffer, 2048, fp)){
    22.             sscanf(buffer, "%s\n", buffer);
    23.            if(!(sym_id = sen_sym_get(sym, buffer))){
    24.                 printf("cannot create link\n");
    25.                 abort();
    26.            }
    27.  
    28. //           printf("%d\t", sym_id);
    29.         }
    30.  
    31.         fclose(fp);
    32.    
    33.         sen_sym_close(sym);
    34.  
    35. }
    36.  
    37. void traverse(char* index, char* filename){
    38.     printf("traverse\n");
    39.     sen_sym* sym;
    40.  
    41.     if(!(sym = sen_sym_open(index))){
    42.         printf("cannot open index file\n");
    43.         abort();
    44.     }
    45.  
    46.     FILE * fp = fopen(filename, "rb");
    47.  
    48.     if(!fp){
    49.         printf("cannot open file\n");
    50.         abort();
    51.     }
    52.  
    53.     fseek(fp, 0, SEEK_END);
    54.  
    55.     int filesize = ftell(fp);
    56.     int offset = 0;
    57.  
    58.     fseek(fp, 0, SEEK_SET);
    59.  
    60.     char * content = new char[filesize + 1];
    61.     const char * cp = content;
    62.  
    63.  
    64.     fread(content, sizeof(char), filesize, fp);
    65.     content[filesize] = '\0';
    66.  
    67.     sen_sym_scan_hit sh[32];
    68.  
    69.     char buffer[2048];
    70.  
    71.     const char * rest;
    72.  
    73.     exectime::start_timer();
    74.  
    75.     while((rest - content) <filesize){
    76.         int found;
    77.         if(!(found = sen_sym_scan(sym, cp, filesize, sh, 32, &rest))){
    78.             break;
    79.         }       
    80.  
    81.         for(int i=0; i<found; i++){
    82.             int key_len = sen_sym_key(sym, sh[i].id, buffer, 2048);
    83.             if(key_len> 0 && sh[i].length> 7){
    84.                printf("%s\n", buffer);
    85.             }
    86.  
    87.         }
    88.         cp = rest;
    89.  
    90.     }
    91.  
    92.     exectime::end_timer();
    93.  
    94.     printf("time: %f sec\n", exectime::time_result());
    95.  
    96.  
    97. }
    98.  
    99. int main(int argc, char** argv){
    100.  
    101.     if(!strcmp(argv[1], "make")){
    102.         create_index(argv[2], argv[3]);
    103.     }else if(!strcmp(argv[1], "traverse")){
    104.         traverse(argv[2], argv[3]);
    105.     }
    106.    
    107. }

  • Comments Off

    • dartsのサイトにのっているサンプルが動かない件

    • Author: harajune
    • Filed under: 雑記
    Tuesday
    Aug 25,2009

    Darts: Double-ARray Trie System

    http://chasen.org/~taku/software/darts/

    dartsというのは、Trie木をdouble arrayで実装したライブラリです。ヘッダファイル一つだけの配布なので大変使いやすい。

    今回HAT-trieを実装してみるにあたって、Trie木の部分の実装としてこれを使ってみることにしました。

    しかし、サンプルが動かない・・・・！どうやらよく見るとテンプレート周りとconstを付け加えた際に、もともとのサンプルが動かなくなった模様。
    なので、これを修正しました。別に大したことはしていません。

    PLAIN TEXT
    CODE:
    1. #include &lt;iostream&gt;
    2. #include &lt;darts.h&gt;
    3.  
    4. int main (int argc, char **argv)
    5. {
    6. using namespace std;
    7.  
    8. const Darts::DoubleArray::key_type   *str[] = { "ALGOL", "ANSI", "ARCO",  "ARPA", "ARPANET", "ASCII" }; // same as char*
    9. Darts::DoubleArray::result_type val[] = { 1, 2, 3, 4, 5, 6 }; // same as int
    10.  
    11. Darts::DoubleArray da;
    12. da.build (6, str, 0, val);
    13.  
    14. cout &lt;&lt;da.exactMatchSearch&lt;int&gt;("ALGOL") &lt;&lt;endl;
    15. cout &lt;&lt;da.exactMatchSearch&lt;int&gt;("ANSI") &lt;&lt;endl;
    16. cout &lt;&lt;da.exactMatchSearch&lt;int&gt;("ARCO") &lt;&lt;endl;
    17. cout &lt;&lt;da.exactMatchSearch&lt;int&gt;("ARPA") &lt;&lt;endl;
    18. cout &lt;&lt;da.exactMatchSearch&lt;int&gt;("ARPANET") &lt;&lt;endl;
    19. cout &lt;&lt;da.exactMatchSearch&lt;int&gt;("ASCII") &lt;&lt;endl;
    20. cout &lt;&lt;da.exactMatchSearch&lt;int&gt;("APPARE") &lt;&lt;endl;
    21.  
    22. da.save("some_file");
    23. }

  • Comments Off

    • about me

    原田　惇

    応用数学や統計、ITなどを利用していろんなことをしています。
    自己紹介はこちら

    adsense

    amazonお勧め

    Tags

    ともだち達

    リンク

    Categories

    Recent Posts


    Recent Comments


    Twitter



    Archives


    Meta


    Copyright © 2007 - 進・日進月歩 - is proudly powered by WordPress
    Smashing Theme is created by: Design Disease brought to you by Smashingmagazine.com