English | Japanese

libsaryリファレンスマニュアル

最終更新日: 2002-10-22 (公開日: 2002-10-22)

サンプルプログラム

Suffix Arrayの構築

file_name のファイルに対して、 UTF-8エンコーディングの文字単位で Suffix Arrayを作成し、ファイル (file_name.ary) に格納する。より詳しい例は mksary.c を参照のこと。

#include <stdlib.h>
#include <errno.h>
#include <sary.h>
  
int
main (int argc, char **argv)
{
    char *file_name;
    SaryInt ipoints;
    gboolean status;
    SaryBuilder *builder;

    if (argc != 2) exit(2);
    file_name = argv[1];

    builder = sary_builder_new(file_name);
    sary_builder_set_ipoint_func(builder, sary_ipoint_char_utf8);

    ipoints = sary_builder_index(builder);
    if (ipoints == -1) {
        g_print("error: %s(.ary): %s\n", file_name, g_strerror(errno));
        exit(2);
    }

    status = sary_builder_sort(builder);
    if (status == FALSE) {
        g_print("error: %s(.ary): %s\n", file_name, g_strerror(errno));
        exit(2);
    }
    sary_builder_destroy(builder);
    return 0;
}

Suffix Arrayを用いた検索

file_name のファイルに対して、pattern で検索を行い、検索結果を出現位置順にソートし、行単位で表示する。検索には file_name 用に構築された Suffix Array が必須。より詳しい例は sary.c を参照のこと。

#include <stdlib.h>
#include <errno.h>
#include <sary.h>

int
main (int argc, char **argv)
{
    SarySearcher *searcher;
    char *pattern;
    char *file_name;

    if (argc != 3) exit(2);
    pattern = argv[1];
    file_name = argv[2];

    searcher = sary_searcher_new(file_name);
    if (searcher == NULL) {
        g_print("error: %s(.ary): %s\n", file_name, g_strerror(errno));
        exit(2);
    }

    if (sary_searcher_search(searcher, pattern)) {
        gchar *line;

        sary_searcher_sort_occurrences(searcher);

        while ((line = sary_searcher_get_next_line(searcher))) {
            g_print("%s", line);
            g_free(line);
        }
    }
    sary_searcher_destroy(searcher);
    return 0;
}

コンパイルの方法

libsary を用いたプログラム program.c をコンパイルするには次のように実行します。本格的な開発には autoconf, automake, libtool の利用をお勧めします。

  % gcc program.c -o program `pkg-config sary --libs` `pkg-config sary --cflags`

Suffix Arrayの構築

SaryBuilder* sary_builder_new (const gchar *file_name): SaryBuilder オブジェクトを生成します。SaryBuilder オブジェクトはインデックスポイントの割り当てと Suffix Array のソートを行いますfile_name には Suffix Array のファイル名を指定します。失敗したときは NULL を返します。
SaryBuilder* sary_builder_new2 (const gchar *file_name, const gchar *array_name);: array_name で Suffix Array のファイル名を指定する以外は sary_builder_new と同様です。
void sary_builder_destroy (SaryBuilder *builder);: SaryBuilder オブジェクトを破壊します。
void sary_builder_set_ipoint_func (SaryBuilder *builder, SaryIpointFunc ipoint_func);: インデックスポイントの割り当てに用いる関数を設定します。 ipoint_func で指定する関数は、標準で用意されている関数を使うだけでなく、SaryIpointFunc のインターフェイスに従って自分で定義した関数を使うこともできます。
SaryInt sary_builder_index (SaryBuilder *builder);: インデックスポイントの割り当てを行います。返り値はとして割り当てたインデックスポイントの数を返します。失敗したときは -1 を返します。
gboolean sary_builder_sort (SaryBuilder *builder);: Suffix Array のソートを行います。成功したときは TRUEを、失敗したときは FALSEを返します。
gboolean sary_builder_block_sort (SaryBuilder *builder);: Suffix Array のソートを行います。ブロック単位で分割してソートを行うため、メモリを節約できます。成功したときは TRUEを、失敗したときは FALSEを返します。
void sary_builder_set_block_size (SaryBuilder *builder, SaryInt block_size);: sary_builder_block_sort 用のブロックサイズを設定します。
void sary_builder_set_nthreads (SaryBuilder *builder, SaryInt nthreads);: sary_builder_block_sort を実行するときのスレッドの数を指定します。CPU が複数ある計算機では速度が向上します。
void sary_builder_connect_progress (SaryBuilder *builder, SaryProgressFunc progress_func, gpointer progress_func_data);: プログレスバーを表示するための関数 progress_func とその関数に必要なデータ progress_func_data を SaryBuilder オブジェクトに結びつけます。

インデックスポイントの割り当て

gchar* sary_ipoint_char_ascii (SaryText *text): ASCII文字 (1オクテット)ごとにインデックスポイントを割り当て、その位置を返します。テキストの末尾まで到達したら NULL を返します。
gchar* sary_ipoint_char_eucjp (SaryText *text): EUC-JPエンコーディングの文字にインデックスポイントを割り当て、その位置を返します。テキストの末尾まで到達したら NULL を返します。
gchar* sary_ipoint_char_sjis (SaryText *text): Shift_JISエンコーディングの文字にインデックスポイントを割り当て割り当て、その位置を返します。テキストの末尾まで到達したら NULL を返します。
gchar* sary_ipoint_char_utf8 (SaryText *text): UTF-8エンコーディングの文字にインデックスポイントを割り当て、その位置を返します。テキストの末尾まで到達したら NULL を返します。
gchar* sary_ipoint_line (SaryText *text): 行単位でインデックスポイントを割り当て、その位置を返します。テキストの末尾まで到達したら NULL を返します。

注意: sary_searcher_search2, sary_searcher_get_next_line2, sary_searcher_get_next_context_lines2, sary_searcher_get_next_tagged_region2 はスクリプト言語用のバンディングを書く人、あるいは効率に熱心な人のために用意されています。これらの関数では文字列は長さとともに扱われるため、'\0' 文字を中に含んでも構いません。新しい文字列が生成されることはありません。

SarySearcher* sary_searcher_new (const gchar *file_name): SarySearcherオブジェクトを生成します。SarySearcherオブジェクトは検索と検索結果の扱いの面倒をみてくれます。SarySearcher は Suffix Array Searcher の略です。 file_nameには検索対象のファイル名を指定します。失敗したときは NULL を返します。
SarySearcher* sary_searcher_new2 (const gchar *file_name, const gchar *array_name): array_name で Suffix Array のファイル名を指定する以外は sary_searcher_new と同様です。
void sary_searcher_destroy (SarySearcher *searcher): SarySearcherオブジェクトを破壊します。
void sary_searcher_enable_cache (SarySearcher *searcher): キャッシュ機構を働かせます。検索結果をキャッシュし、同じパターンでの 2度目以降の検索を高速化します。
gboolean sary_searcher_search (SarySearcher *searcher, const gchar *pattern): 検索を行います。pattern には検索のキーワードを指定します。成功したときは TRUEを、失敗したときは FALSE を返します。
gboolean sary_searcher_search2 (SarySearcher *searcher, const gchar *pattern, SaryInt len): pattern の長さ len を指定して検索を行います。pattern には検索のキーワードを指定します。成功したときは TRUEを、失敗したときは FALSE を返します。
gboolean sary_searcher_isearch (SarySearcher *searcher, const gchar *pattern, SaryInt len): sary_searcher_search2 とほぼ同じですが、この関数は効率のよいインクリンタル検索を行います。検索は前回の検索結果の範囲の中で行われます (初回は sary_searcher_search2 と同じ動作をします)。pattern を固定して、lenの値をpattern の長さまで徐々に大きくしながら連続して呼び出すことによりインクリメンタル検索ができます。 sary_searcher_sort_occurrences との併用はできません。成功したときは TRUEを、失敗したときは FALSE を返します。
gboolean sary_searcher_isearch_reset (SarySearcher *searcher): sary_searcher_isearch 用の内部状態をリセットします。新たな pattern で sary_searcher_isearch を呼び出すときは、事前にこの関数を実行して内部状態をリセットしてください。
gboolean sary_searcher_icase_search (SarySearcher *searcher, const gchar *pattern): アルファベットの大文字小文字を区別しない検索を行います。 pattern には検索のキーワードを指定します。成功したときは TRUEを、失敗したときは FALSE を返します。
gboolean sary_searcher_icase_search2 (SarySearcher *searcher, const gchar *pattern, SaryInt len): pattern の長さ len を指定してアルファベットの大文字小文字を区別しない検索を行います。pattern には検索のキーワードを指定します。成功したときは TRUEを、失敗したときは FALSE を返します。
SaryText* sary_searcher_get_text (SarySearcher *searcher): 検索対象の SaryText オブジェクトを返します。
SaryMmap* sary_searcher_get_array (SarySearcher *searcher): mmap された Suffix Array を返します。
gchar* sary_searcher_get_next_line (SarySearcher *searcher): 次の検索結果を行単位で新しい文字列として取り出します。この関数を連続して呼ぶと、すべての検索結果が得られます。残りの検索結果がないときは NULL を返します。返り値は後から g_free する必要があります。
gchar* sary_searcher_get_next_line2 (SarySearcher *searcher, SaryInt *len): 次の検索結果を行単位で先頭位置のポインタとして取り出します。文字列の長さをlen に書き込みます。この関数を連続して呼ぶと、すべての検索結果が得られます。残りの検索結果がないときは NULL を返します。
gchar* sary_searcher_get_next_context_lines (SarySearcher *searcher, SaryInt backward, SaryInt forward): 次の検索結果をコンテクスト行単位で新しい文字列として取り出します。最後の改行記号 '\n' は文字列に含みます。この関数を連続して呼ぶと、すべての検索結果が得られます。残りの検索結果がないときは NULL を返します。返り値は後から g_free する必要があります。
gchar* sary_searcher_get_next_context_lines2 (SarySearcher *searcher, SaryInt backward, SaryInt forward, SaryInt *len): 次の検索結果をコンテクスト行単位で先頭位置のポインタとして取り出します。最後の改行記号 '\n' は文字列に含みます。文字列の長さをlen に書き込みます。この関数を連続して呼ぶと、すべての検索結果が得られます。残りの検索結果がないときは NULL を返します。
gchar* sary_searcher_get_next_tagged_region (SarySearcher *searcher, const gchar *start_tag, const gchar *end_tag): 次の検索結果を start_tag と end_tag で挟まれた範囲の新しい文字列として取り出します (start_tag と end_tag を含みます)。この関数を連続して呼ぶと、すべての検索結果が得られます。残りの検索結果がないときは NULL を返します。返り値は後から g_free する必要があります。
gchar* sary_searcher_get_next_tagged_region2 (SarySearcher *searcher, const gchar *start_tag, SaryInt start_tag_len, const gchar *end_tag, SaryInt end_tag_len, SaryInt *len): 次の検索結果を start_tag と end_tag で挟まれた範囲の先頭位置をポインタとして取り出します (start_tag と end_tag を含みます)。文字列の長さをlen に書き込みます。start_tag と end_tag の長さをそれぞれ start_tag_len とend_tag_len で指定します。この関数を連続して呼ぶと、すべての検索結果が得られます。残りの検索結果がないときは NULL を返します。
SaryText* sary_searcher_get_next_occurrence (SarySearcher *searcher): 次の検索結果を SaryText オブジェクトとして返します。低レベルのテキスト処理を行う際に用います。この関数を連続して呼ぶと、すべての検索結果が得られます。残りの検索結果がないときは NULL を返します。
SaryInt sary_searcher_get_next_occurrence (SarySearcher *searcher): 次の検索結果を SaryInt の値として返します。この関数を連続して呼ぶと、すべての検索結果が得られます。残りの検索結果がないときは -1 を返します。
SaryInt sary_searcher_count_occurrences (SarySearcher *searcher): 検索のヒット数を返します。
void sary_searcher_sort_occurrences (SarySearcher *searcher): 検索結果を出現位置順にソートします。

テキスト処理

テキスト処理には SaryText オブジェクトを利用します。このオブジェクトはカーソルという状態を持っており、オブジェクトに対する操作はこのカーソルを元にして行われます。

SaryText* sary_text_new (const gchar *file_name): file_name 用の SaryTextオブジェクトを生成します。失敗したときは NULL を返します。
void sary_text_destroy (SaryText *text): SaryTextオブジェクトを破壊します。
SaryInt sary_text_get_lineno (SaryText *text): カーソル位置の行番号を返します。(libsaryではほとんど使い道がありません)
void sary_text_set_lineno (SaryText *text, SaryInt lineno): カーソル位置の行番号を設定します。(libsaryではほとんど使い道がありません)
SaryInt sary_text_get_linelen (SaryText *text): カーソル位置の行の長さを返します。行の長さに改行記号 '\n' は含みません。カーソルがファイル末尾にあるときは 0 を返します。
gchar* sary_text_get_line (SaryText *text): カーソル位置の行を新しい文字列として返します。改行記号 '\n' は文字列に含みます。カーソルがファイル末尾にあるときは NULL を返します。返り値は後から g_free する必要があります。
gchar* sary_text_get_region (SaryText *cursor, SaryInt len): カーソル位置から len 文字分の領域を新しい文字列として返します。返り値は後から g_free する必要があります。
gboolean sary_text_is_eof (SaryText *text): カーソルがファイルの末尾の位置にあれば TRUEを、そうでなければ FALSE を返します。
gchar* sary_text_get_cursor (SaryText *text): カーソルの位置を返します。
void sary_text_set_cursor (SaryText *text, gchar *cursor): カーソルの位置を設定します。
gchar* sary_text_get_bof (SaryText *text): ファイルの先頭の位置を返します。
gchar* sary_text_get_eof (SaryText *text): ファイルの末尾の位置を返します。
gchar* sary_text_goto_bol (SaryText *text): カーソルを行頭に進めます。移動後のカーソルの位置を返します。
gchar* sary_text_goto_eol (SaryText *text): カーソルを行末に進めます。移動後のカーソルの位置を返します。
gchar* sary_text_goto_next_line (SaryText *text): カーソルを次の行に進めます。移動後のカーソルの位置を返します。
gchar* sary_text_goto_next_word (SaryText *text): カーソルを次の単語に進めます。単語は空白によって区切られた文字列です。移動後のカーソルの位置を返します。
gchar* sary_text_forward_cursor (SaryText *text, SaryInt len): カーソルを len バイト進めます。移動後のカーソルの位置を返します。
gchar* sary_text_backward_cursor (SaryText *text, SaryInt len): カーソルを len バイト後退します。移動後のカーソルの位置を返します。

プログレスバーの表示

mksary.c の progress_bar 関数を参考にしてください。

付録: スクリプト言語の活用

インデックスポイントの割り当ては Perl などのスクリプト言語で簡単に行うことができます。複雑なテキスト処理を要するときはスクリプト言語を利用すると便利です。次の例は行頭にインデックスポイントを割り当てる例です。

  % cat line-indexer.pl
  $offset = 0;
  while (<>) {
      print pack 'N', $offset;
      $offset += length;
  }

  % perl line-indexer.pl foobar.txt > foobar.txt.ary

このようにして作成した foobar.txt.ary ファイルを mksary -s でソートすれば、 Suffix Array が完成します。

  % mksary -s foobar.txt

Satoru Takabayashi

libsaryリファレンスマニュアル

目次