プーシキン・電子コンコーダンス自動生成プログラム Опыт динамического составления конкордации к текстам А. С. Пушкина の再構築設計で，巨大なコーパス，ワード・バイナリツリー（二分木）を複数のユーザで共有しかつ高速に処理するための方式として，これらを UNIX 共有メモリ（Shared Memory）に格納することを考えた。shmget() などの UNIX システムコールを使うことも視野に入れたのだが，いまさらシステムコールで低レベルの操作（ソフトウェアの世界では「低レベル」というコトバは，実世界で纏わり着く「蔑み」の意味はまったくない。ハードウェア，オペレーティングシステムに近い部分を扱う意味で，逆に「高度」な専門知識が要求される — 計算機の世界ではいろんな事柄が現実世界と反転するのだ！）なんかしなくても，便利なフリーのライブラリがあるはずで，そちらの線で調査をした。ありました — Boost.
Boost はオープンソースの有名な C++ ライブラリである。私もその正規表現ライブラリ Boost.
コンコーダンスのワード・ツリーは，単語をキーにしてその出現回数，位置情報，別単語ノードへのポインタを保持するノード群で構成され，各ノードがルート（根）から左右のポインタで繋がっている（当該ノードの単語より辞書順で小さいノードを左ポインタ，大きいノードを右ポインタでポイントして，全ノードが木構造で繋がっている。こうすることにより，どのノードにも log N 対数計算量で — 単語数が 10000 倍になっても 3 倍程度しか検索速度が低下しない — 高速アクセスが実現できる）というデータ構造である。これを共有メモリに格納できるかが私の課題だった。int や float といった数値データはマニュアルや Boost 関連のネット情報を参考に簡単にできることがわかったが，string，つまり文字列データを共有メモリに格納して他プロセスから参照することがうまく行かない。string オブジェクトがフリーストアに生成されてしまい，他プロセスからアクセスできないのである。どうも私の allocator の使い方がまずいようだった。ビャーネ・ストラウストラップ『プログラミング言語 C++』の関連する頁を読み直し，Boost マニュアル Allocators, containers and memory allocation algorithms を丹念に読んで，ようやく解決することができた。
ロシア語テキストから単語を切り出し，共有メモリに単語（キー）：数値からなる map を構築するサーバ shmsrv.
// -*- coding: utf-8; mode: c++; -*- // shmdt.h: shared memory test header #ifndef MY_SHARED_MEMORY_ALLOCATOR #define MY_SHARED_MEMORY_ALLOCATOR #include <boost/interprocess/managed_shared_memory.hpp> #include <boost/interprocess/allocators/allocator.hpp> #include <boost/interprocess/containers/map.hpp> #include <boost/interprocess/containers/vector.hpp> #include <boost/interprocess/containers/string.hpp> #include <iostream> #include <sstream> // Typedefs of allocators and containers using namespace boost::interprocess; typedef managed_shared_memory::segment_manager segment_manager_t; typedef allocator<void, segment_manager_t> void_allocator; typedef allocator<int, segment_manager_t> int_allocator; typedef vector<int, int_allocator> int_vector; typedef allocator<int_vector, segment_manager_t> int_vector_allocator; typedef vector<int_vector, int_vector_allocator> int_vector_vector; typedef allocator<char, segment_manager_t> char_allocator; typedef basic_string<char, std::char_traits<char>, char_allocator> char_string; typedef std::pair<const char_string, int> map_value_type; typedef std::pair<char_string, int> movable_to_map_value_type; typedef allocator<map_value_type, segment_manager_t> map_value_type_allocator; typedef map<char_string, int, std::less<char_string>, map_value_type_allocator> complex_map_type; typedef complex_map_type::const_iterator It; // shared memory const static const char* SHMNAME = "MySharedMemory"; static const int SHMSIZE = 4 * 1024; #endif
// -*- coding: utf-8; mode: c++; -*-
// サーバ Server of Map in Shared Memory
#include <csignal>
#include "shmdt.h"
// 共有メモリを開始前と終了後に削除する remover
struct shm_remove
{
shm_remove() {
std::cout << "remover construction.\n";
shared_memory_object::remove(SHMNAME);
}
~shm_remove(){
std::cout << "remover deconstruction.\n";
shared_memory_object::remove(SHMNAME);
}
} remover;
// テキストファイルから単語を切り出して vector に格納するスキャナ
void scan(vector<string>& sv, const char* const name)
{
int ch; // current character
string new_word; // word we are working on
std::ifstream in_file; // input file
// input text file
in_file.open(name, std::ios::in);
if (in_file.bad()) {
std::cerr << "Error: Unable to open " << name << "\n";
exit(8);
}
// 単語を切り出し，vector にストア
while (true) {
// scan past the whitespace
while (true) {
ch = in_file.get();
if (!std::isspace(ch) || (ch == EOF)) break;
}
if (ch == EOF) break;
new_word = ch;
while (true) {
ch = in_file.get();
if (std::isspace(ch) || std::ispunct(ch)) break;
new_word += ch;
}
sv.push_back(new_word);
}
}
// シグナル・ハンドラ
void term(int n) {
std::cout << "Signal caught " << n << "\n";
exit(1);
}
// メイン
int main ()
{
// 共有メモリを確保し，そのオブジェクトを取得
managed_shared_memory segment(create_only, SHMNAME, SHMSIZE);
void_allocator alloc_inst (segment.get_segment_manager());
// 共有メモリ上に map を構築
complex_map_type* mymap = segment.construct<complex_map_type>
//(object name), (first ctor parameter, second ctor parameter)
("MyMap")(std::less<char_string>(), alloc_inst);
// スキャナによってテキストを string vector に格納
vector<string> words;
scan(words, "sample.txt");
// 単語情報を map に登録（mapped データは試験的に格納順序番号とする）
int num = 0;
for (vector<string>::iterator it = words.begin();
it != words.end(); it++) {
char_string key_object(alloc_inst);
key_object = (*it).c_str();
map_value_type value(key_object, num);
mymap->insert(value);
std::cout << "sv map: " << *it << ":" << num++ << "\n";
}
// map のアドレスを連絡するためのハンドルを取得
void* p = static_cast<void*>(mymap);
managed_shared_memory::handle_t handle =
segment.get_handle_from_address(p);
std::cout << "sv handle: " << handle << "\n";
// 捕捉シグナルとハンドラの登録
signal(SIGTERM, term);
signal(SIGINT, term);
signal(SIGHUP, term);
// シグナルを受信するか何か入力されるまでウェイト
while (true) {
std::cout << "Wait. Signal (TERM, INT, HUP) or any key to exit.\n";
char x; std::cin >> x; break;
}
return 0;
}
// -*- coding: utf-8; mode: c++; -*-
// クライアント Client of Map in Shared Memory
#include "shmdt.h"
int main (int argc, char* argv[])
{
// 共有メモリ・オブジェクトを取得
managed_shared_memory segment(open_only, SHMNAME);
// ハンドルから共有メモリ・リソースのアドレスを取得
managed_shared_memory::handle_t handle = 0;
std::stringstream s; s << argv[1]; s >> handle;
void* vp = segment.get_address_from_handle(handle);
// void ポインタを map ポインタにキャストし，map を参照
complex_map_type* mp = static_cast<complex_map_type*>(vp);
std::cout << "cl map address: " << mp << "\n";
for (It p = mp->begin(); p != mp->end(); p++)
std::cout << "cl map: " << p->first << ":" << p->second << "\n";
return 0;
}
GNU C++ コンパイラでサーバ，クライアントをコンパイルする。
% g++ -g -I/usr/local/include -L/usr/local/lib -o shmsrv shmsrv.cpp \ -lboost_system % g++ -g -I/usr/local/include -L/usr/local/lib -o shmclt shmclt.cpp \ -lboost_system
試験で使ったテキストデータは次の通り。
Мой дядя самых честных правил, Когда не в шутку занемог, Он уважать себя заставил И лучше выдумать не мог.
サーバを起動すると，上記データを読んで単語を切り出し，登録順に単語を出力し，共有メモリ・ハンドルを表示し，ウェイトする。
% shmsrv
remover construction.
sv map: Мой:0
sv map: дядя:1
sv map: самых:2
sv map: честных:3
sv map: правил:4
sv map: Когда:5
sv map: не:6
sv map: в:7
sv map: шутку:8
sv map: занемог:9
sv map: Он:10
sv map: уважать:11
sv map: себя:12
sv map: заставил:13
sv map: И:14
sv map: лучше:15
sv map: выдумать:16
sv map: не:17
sv map: мог:18
sv handle: 148
Wait. Signal (TERM, INT, HUP) or any key to exit.
引き続いて，クライアントを起動する。このときサーバが表示した共有メモリ・ハンドルを引数に指定することにより，アクセスすべきアドレスを引き当てるようになっている。map を iterator で回して出力するので，キーの小さいものから単語と数値を表示する。共有メモリ上の情報を他のプロセスからでも読み取れることが確認できる。
% shmclt 148 cl map address: 0x16d094 cl map: И:14 cl map: Когда:5 cl map: Мой:0 cl map: Он:10 cl map: в:7 cl map: выдумать:16 cl map: дядя:1 cl map: занемог:9 cl map: заставил:13 cl map: лучше:15 cl map: мог:18 cl map: не:6 cl map: правил:4 cl map: самых:2 cl map: себя:12 cl map: уважать:11 cl map: честных:3 cl map: шутку:8
サーバを停止する。シグナル SIGTERM を送った場合，次のメッセージとともに終了する。remover が確保した共有メモリの後始末をする。
Signal caught 15 remover deconstruction.
同じコードで Mac OS X Snow Leopard と FreeBSD 8.2-RELEASE で動作した。これで私の課題の核の部分は解決した。実際の設計では，単語についてロシア語 Lemmatizer で見出し語に変換したものをキーとし，上記登録数値の代わりに単語出現回数，出現位置情報リンクリストをキーにぶら下げればよい。STL の map は二分木アルゴリズムに基づいているので，実際のコンコーダンスでも使用するだろう（現行版コンコーダンスでは自前で二分木を構築している）。
それにしても，ちょっと曲がった特殊な課題に取り組むとき，ネットの情報（ブログ，プログラミング・サイト記事）は役に立たないことが多い。自分の課題解決のためには，やっぱり当該ソフトウェアのマニュアル，権威ある言語解説書を丹念に読まないといけない。今回もこれを思い知った。B. ストラウストラップによる『プログラミング言語 C++ 第 3 版』はこういうときに立ち還るべき名著だと納得したんである。
長尾高弘訳
アジソン・ウェスレイ・パブリッシャーズ・ジャパン