WordTree.cpp

/* */
This source file includes following definitions.
getgenre
getfileno
getlineno
getlineid
getlinepos
getwordpos
getnextptr
compadjacent
printwpos
setwpos
enter_node
setwordinfo
print_node
find_node
find_node_set
find_regex_node_set
find_adjacent_node_set
   1 /* -*- coding: utf-8; mode: c++; -*-
   2  * Concordance to A. S. Pushkin's Works - Word Tree Class
   3  * $Id: WordTree.cpp 1 2012-06-02 08:43:50Z isao $
   4  * Copyright (C) 2012, isao yasuda
   5  */
   6 
   7 #include "SharedMemoryCommon.hpp"
   8 #include "SharedMemoryTree.hpp"
   9 
  10 using namespace boost::interprocess;
  11 
  12 // 共有メモリ内アロケーションポインタ
  13 char* ShmP;
  14 
  15 // 単語位置情報クラスメンバ取得
  16 int  wpos::getgenre()
  17 {
  18     return genre;    // genre
  19 }
  20 int  wpos::getfileno()
  21 {
  22     return fname;    // fname
  23 }
  24 int  wpos::getlineno()
  25 {
  26     return linno;    // linno
  27 }
  28 int  wpos::getlineid()
  29 {
  30     return linid;    // linid
  31 }
  32 int  wpos::getlinepos()
  33 {
  34     return linps;    // linps
  35 }
  36 int  wpos::getwordpos()
  37 {
  38     return wdpos;    // wdpos
  39 }
  40 offset_ptr<wpos> wpos::getnextptr()
  41 {
  42     return next;    // next pointer
  43 }
  44 
  45 // 位置情報比較
  46 void wpos::compadjacent(std::vector<offset_ptr<wpos> >& pv1,
  47                         std::vector<offset_ptr<wpos> >& pv2,
  48                         std::vector<offset_ptr<wpos> >& rv,
  49                         int kind, int dist)
  50 {
  51     std::vector<offset_ptr<wpos> > qv; // 適合位置情報ポインタの vector
  52     int delta; // 語／行アドレスの差分
  53 
  54     for (std::vector<offset_ptr<wpos> >::iterator pi1 = pv1.begin();
  55             pi1 != pv1.end(); pi1++) {
  56         if (kind == 1) { // 語アドレスの比較
  57             for (std::vector<offset_ptr<wpos> >::iterator pi2 = pv2.begin();
  58                     pi2 != pv2.end(); pi2++) {
  59                 // 作品番号が同一かつ位置情報差分が非 0 の dist 範囲内の wpos を収集
  60                 if ((*pi1)->getfileno() == (*pi2)->getfileno()) {
  61                     delta = std::abs
  62                             ((*pi1)->getwordpos() - (*pi2)->getwordpos());
  63                     if ((delta <= dist) && (delta != 0))
  64                         rv.push_back(*pi1);
  65                 }
  66             }
  67         } else {         // 行アドレスの比較
  68             for (std::vector<offset_ptr<wpos> >::iterator pi2 = pv2.begin();
  69                     pi2 != pv2.end(); pi2++) {
  70                 // 作品番号が同一かつ位置情報差分が非 0 の dist 範囲内の wpos を収集
  71                 if ((*pi1)->getfileno() == (*pi2)->getfileno()) {
  72                     delta = std::abs
  73                             ((*pi1)->getlineno() - (*pi2)->getlineno());
  74                     if ((delta <= dist) && (delta != 0))
  75                         rv.push_back(*pi1);
  76                 }
  77             }
  78         }
  79     }
  80 }
  81 
  82 // 位置情報出力: 全ての位置情報を出力する
  83 void wpos::printwpos()
  84 {
  85     if (this != NULL) {
  86         std::cout << genre << ":" << fname << ":" << linno << ":"
  87                   << linid << ":" << linps << ":" << wdpos << "; ";
  88         next->wpos::printwpos();
  89     } else {
  90         std::cout << "\n";
  91     }
  92 }
  93 
  94 // 位置情報 vector セット: 適合ジャンルの位置情報を vector に追加する
  95 void wpos::setwpos(std::vector<offset_ptr<wpos> >& wpv,
  96                    std::vector<int>& gv)
  97 {
  98     // 指定ジャンルに適合する位置情報を引数の vector に登録
  99     if (gv.size() == 0)
 100         wpv.push_back(this);
 101     else
 102         for (std::vector<int>::iterator vi = gv.begin();
 103                 vi != gv.end(); vi++)
 104             if (*vi == genre) // 適合
 105                 wpv.push_back(this);
 106 }
 107 
 108 // ノード登録:
 109 void tree::enter_node(offset_ptr<node>& new_node, const std::string& new_word,
 110                       int gi, int fi, int li, int ii, int pi, int wi)
 111 {
 112     // 登録単語サイズ
 113     size_t sz = new_word.size() + 1;
 114 
 115     // ノードポインタが NULL の場合: 新規登録
 116     if (new_node == NULL) {
 117         // 新しい node を生成
 118         new_node = new(reinterpret_cast<node*>(ShmP)) node;
 119         ShmP += sizeof(node); // ポインタ更新
 120         // 左右ポインタ初期化
 121         new_node->left  = NULL;
 122         new_node->right = NULL;
 123         // 単語登録
 124         new_node->word  = new(ShmP) char[sz];
 125         std::strcpy((char*) ShmP, new_word.c_str());
 126         ShmP += sz; // ポインタ更新
 127         // カウンタ初期化
 128         new_node->counter = 1;
 129         // wpos 初期登録
 130         new_node->fpos = new(reinterpret_cast<wpos*>(ShmP))
 131         wpos(gi, fi, li, ii, pi, wi);
 132         new_node->lpos = new_node->fpos;
 133         ShmP += sizeof(wpos); // ポインタ更新
 134         wordt++; // 異なり処理単語数更新
 135         return;
 136     }
 137 
 138     // offset_ptr を char* に変換
 139     char* wp = (new_node->word).get();
 140 
 141     // 既登録の単語と一致した場合: カウンタをアップし，位置情報を追加
 142     if (std::strcmp(wp, new_word.c_str()) == 0) {
 143         new_node->counter += 1;
 144         (new_node->lpos)->next = new(reinterpret_cast<wpos*>(ShmP))
 145         wpos(gi, fi, li, ii, pi, wi);
 146         new_node->lpos = (new_node->lpos)->next;
 147         ShmP += sizeof(wpos); // ポインタ更新
 148         return;
 149     }
 150 
 151     // 既登録単語より辞書順で後なら右ノードへ，前なら左ノードへ
 152     if (std::strcmp(wp, new_word.c_str()) < 0)
 153         enter_node(new_node->right, new_word, gi, fi, li, ii, pi, wi);
 154     else
 155         enter_node(new_node->left,  new_word, gi, fi, li, ii, pi, wi);
 156 }
 157 
 158 // ノード情報セット
 159 void tree::setwordinfo(wordinfo& winfo, std::vector<int>& gv,
 160                        offset_ptr<node>& tnode)
 161 {
 162     // ノードポインタが NULL ならそこで終了
 163     if (tnode == NULL) return;
 164 
 165     // 対象ジャンルのみでカウンタ，位置情報をすげ替える
 166     winfo.word = tnode->word;
 167     offset_ptr<wpos> wptr = tnode->fpos;
 168     while (wptr != NULL) {
 169         wptr->setwpos(winfo.wposv, gv);
 170         wptr = wptr->next;
 171     }
 172     winfo.counter = winfo.wposv.size();
 173 }
 174 
 175 // ノード印字
 176 void tree::print_node(offset_ptr<node>& top)
 177 {
 178     // ノードポインタが NULL ならそこで終了
 179     if (top == NULL) return;
 180 
 181     // 左ノードを出力
 182     print_node(top->left);
 183 
 184     // 現ノードを出力
 185     char* wp = (top->word).get(); // offset_ptr を char* に変換
 186     std::cout << wp << " " << top->counter << " ";
 187     (top->fpos)->printwpos();
 188 
 189     // 右ノードを出力
 190     print_node(top->right);
 191 }
 192 
 193 // ノード完全一致探索
 194 void tree::find_node(const std::string& tword, offset_ptr<node>& tnode)
 195 {
 196     // ノードポインタが NULL ならそこで終了
 197     if (tnode == NULL) return;
 198 
 199     // offset_ptr を char* に変換
 200     char* wp = (tnode->word).get();
 201 
 202     // 指定単語に一致したら現ノードを出力
 203     if (std::strcmp(wp, tword.c_str()) == 0) {
 204         std::cout << wp << " " << tnode->counter << " ";
 205         (tnode->fpos)->printwpos();
 206         return;
 207     }
 208 
 209     // 既登録単語より辞書順で後なら右ノード，前なら左ノードを探索
 210     if (std::strcmp(wp, tword.c_str()) < 0)
 211         find_node(tword, tnode->right);
 212     else
 213         find_node(tword, tnode->left);
 214 }
 215 
 216 // ノード完全一致探索 vector set
 217 void tree::find_node_set(const std::string& tword, std::vector<wordinfo>& nv,
 218                          std::vector<int>& gv, offset_ptr<node>& tnode)
 219 {
 220     // ノードポインタが NULL ならそこで終了
 221     if (tnode == NULL) return;
 222 
 223     // offset_ptr を char* に変換
 224     char* wp = (tnode->word).get();
 225 
 226     // 指定単語に一致したら現ノードを vector に追加
 227     if (std::strcmp(wp, tword.c_str()) == 0) {
 228         // 指定ジャンルに一致するものだけを単語情報構造体に wn にセットする
 229         wordinfo wn;
 230         setwordinfo(wn, gv, tnode);
 231         // 呼び出し元単語情報 vector に追加
 232         if (wn.counter != 0)
 233             nv.push_back(wn);
 234         return;
 235     }
 236 
 237     // 既登録単語より辞書順で後なら右ノード，前なら左ノードを探索
 238     if (std::strcmp(wp, tword.c_str()) < 0)
 239         find_node_set(tword, nv, gv, tnode->right);
 240     else
 241         find_node_set(tword, nv, gv, tnode->left);
 242 }
 243 
 244 // ノード正規表現探索
 245 void tree::find_regex_node_set(boost::u32regex& reg, std::vector<wordinfo>& nv,
 246                                std::vector<int>& gv, offset_ptr<node>& tnode)
 247 {
 248     // ノードポインタが NULL ならそこで終了
 249     if (tnode == NULL) return;
 250 
 251     // 左ノードを正規表現探索
 252     find_regex_node_set(reg, nv, gv, tnode->left);
 253 
 254     // 現ノードのパターンマッチ
 255     boost::smatch m; // マッチ結果
 256     char* wp = (tnode->word).get(); // offset_ptr を char* に変換
 257     if (boost::u32regex_match(wp, m, reg)) {
 258         // 指定ジャンルに一致するものだけを単語情報構造体に wn にセットする
 259         wordinfo wn;
 260         setwordinfo(wn, gv, tnode);
 261         // 呼び出し元単語情報 vector に追加
 262         if (wn.counter != 0)
 263             nv.push_back(wn);
 264     }
 265 
 266     // 右ノードを正規表現探索
 267     find_regex_node_set(reg, nv, gv, tnode->right);
 268 }
 269 
 270 // ノード近接隣接探索
 271 void tree::find_adjacent_node_set(const std::string& adj1,   // 検査ワード
 272                                   const std::string& adj2,   // 近接隣接ワード
 273                                   int kind, // 種別 0:行数; 1:単語数;
 274                                   int dist, // 距離
 275                                   std::vector<wordinfo>& nv, // 結果 vector
 276                                   std::vector<int>& gv,
 277                                   offset_ptr<node>& tnode)
 278 {
 279     // ノードポインタが NULL ならそこで終了
 280     if (tnode == NULL) return;
 281 
 282     std::vector<wordinfo> adjv1, adjv2;
 283     boost::u32regex r(boost::make_u32regex("[\\-+*^$.|,?()\\[\\]{}\\\\]"));
 284     boost::u32regex rk(boost::make_u32regex(adj1.c_str()));
 285     boost::u32regex ra(boost::make_u32regex(adj2.c_str()));
 286     boost::smatch   m; // マッチ結果
 287 
 288     // 検査ワード(KW): 適合するものを adjv1 に蓄積
 289     if (boost::u32regex_search(adj1.c_str(), m, r))
 290         find_regex_node_set(rk, adjv1, gv, tnode);
 291     else
 292         find_node_set(adj1, adjv1, gv, tnode);
 293     if (adjv1.size() == 0)
 294         return;
 295 
 296     // 近接隣接ワード(AW): 適合するものを adjv2 に蓄積
 297     if (boost::u32regex_search(adj2.c_str(), m, r))
 298         find_regex_node_set(ra, adjv2, gv, tnode);
 299     else
 300         find_node_set(adj2, adjv2, gv, tnode);
 301     if (adjv2.size() == 0)
 302         return;
 303 
 304     // KW の語情報構造体ごとに位置情報をマッチングする
 305     for (std::vector<wordinfo>::iterator n1it = adjv1.begin();
 306             n1it != adjv1.end(); n1it++) {
 307         std::vector<offset_ptr<wpos> > rv;
 308         // KW の位置情報ごとに AW と比較し，適合する位置情報を収集する
 309         for (std::vector<wordinfo>::iterator n2it = adjv2.begin();
 310                 n2it != adjv2.end(); n2it++) {
 311             wpos::compadjacent((*n1it).wposv, (*n2it).wposv, rv, kind, dist);
 312         }
 313         // 適合単語位置情報があればヒット語情報に登録
 314         if (rv.size()) {
 315             wordinfo adjinf;             // 適合単語情報
 316             adjinf.word    = n1it->word; // 検査中の語
 317             adjinf.counter = rv.size();  // 近接隣接適合カウンタ
 318             adjinf.wposv   = rv;
 319             nv.push_back(adjinf);
 320         }
 321     }
 322 }
 323
/* */
root/WordTree.cpp

DEFINITIONS
