perl - Text::Tx now released!

以前作って放置してあったText::Tx を、CPAN にも Release したのでお知らせします。

• /lang/perl/Text-Tx/L/trunk - CodeRepos::Share - Trac
• Dan Kogai / Text-Tx/ - search.cpan.org
• http://www.dan.co.jp/~dankogai/cpan/Text-Tx-0.02.tar.gz

404 Blog Not Found:perl - Text::Tx も一応作った

CPANにまだ上げない理由その一。txはlibraryとして素直に使うにはちょっと問題があるのです。

もう一つは、なぜか Mac OS X v10.4.11 の gcc 4.0できちんとcompileしないこと。署名の後に様子を張っておきますが、なんだかむずがってます。

この問題が双方解決したためです。

で、これの使いどころですが、やはりこういうアプリケーションになるでしょう。

404 Blog Not Found:Ajax - linkjawiki

小飼弾（こがい　だん、1969年8月17日 - ）は日本のオープンソース開発者。ディーエイエヌ有限会社代表取締役。歌代和正開発のjcode.plの発想を基にJcode.pmを開発したことで知られ、その後、プロジェクトEncode Module(Encode.pm）のメンテナンスとPerlバージョン5.8の開発に携わった。そうした経緯から日本のPerlハッカーの一人と認知されている。

これと同様のことは、正規表現を使っても理論上はできるのですが、何十万もの単語にmatchするものはあまりにメモリーを食ってしまいます。/usr/share/dict/wordsぐらいなら、

• 404 Blog Not Found:TRIE-Optimized Regexp

のようになんとか正規表現でも間に合いますが、Wikipediaの見出し語ともなるともうお手上げです。しかし、Txを使えば、正規表現はおろか、もとのデータ量より少ないメモリーで同様のことを実現できるので、オンメモリーで同様のことが出来るのです。

Tx: Succinct Trie Data Structure

TxはコンパクトなTrieを構築するためのライブラリです．従来のTrieの実装（darts等）に比べ1/4〜1/10の作業領域量で辞書を保持することができ、数億〜十億キーワードなど大規模な辞書を扱うことが可能です．Trieは文字列からなるキー集合を処理するデータ構造で、キーが辞書に含まれているかのみではなく、キーのPrefixが含まれているかを高速に求めることができます．内部データ構造にはSuccinct Data StructureであるLevel-Order Unary Degree Sequence (LOUDS)を利用しています．

で、OS Xに対応させた方法ですが、こうしました。

--- Tx.xs	(revision 30412)
+++ Tx.xs	(working copy)
@@ -1,4 +1,5 @@
 #ifdef __cplusplus
+#include <iostream>
 extern "C" {
 #endif
 #include "EXTERN.h"
@@ -8,7 +9,7 @@
 }
 #endif

要は、perl関連の*.hのファイルの前に<iostream>を読み込むことで、tx.hpp中で<iostream>をincludeされるときのエラーを回避した、というわけです。PerlでC++なXSを作るときのtipとして使えるかもしれません。

他はだいたい

Perl and C++

を読めば、XSに慣れている人ならC++でもなんとかいけるかもです。

というわけで、Releaseです。

NAME
    Text::Tx - Perl interface to Tx by OKANOHARA Daisuke

SYNOPSIS
      use Text::Tx; 
      my $td     = Text::Tx->open("words.tx");
      my $newstr = $td->gsub($str, sub{ 
         qq($_[0])
      }); # link'em all!

DESCRIPTION
    Tx is a library for a compact trie data structure by OKANOHARA Daisuke.
    Tx requires 1/4 - 1/10 of the memory usage compared to the previous
    implementations, and can therefore handle quite a large number of keys
    (e.g. 1 billion) efficiently.

    Suppose words.tx is a pre-built tx by txbuild command which contains
    foo, bar, and baz,

      $newstr = $td->gsub($str, sub{"<$_[0]>"});

    is equivalent to

      my $newstr = $str;
      $newstr = s{ (foo|bar|baz) }{ "<<$1>" }msgex;

    Sounds less convenient? But what happens if the alteration contains
    thousands of words? It takes a whole lot of time and memory just to
    compile the regexp. Tx and Text::Tx does just that.

REQUIREMENT
    Tx 0.04 or above. Available at

    

    To install, just

      fetch http://www-tsujii.is.s.u-tokyo.ac.jp/~hillbig/software/tx-0.04.tar.gz
      tar zxvf tx-0.04.tar.gz
      cd tx-0.04
      configure
      make
      sudo make install

  EXPORT
    None.

SEE ALSO
    

    Regexp::Assemble

AUTHOR
    Dan Kogai, 

COPYRIGHT AND LICENSE
    Copyright (C) 2007 by Dan Kogai

    This library is free software; you can redistribute it and/or modify it
    under the same terms as Perl itself, either Perl version 5.10.0 or, at
    your option, any later version of Perl 5 you may have available.

Enjoy!

Dan the Trie Monger