Category: Algorithm

The Jaccard index, also known as the Jaccard similarity coefficient (originally coined coefficient de communauté by Paul Jaccard), is a statistic used for comparing the similarity and diversity of sample sets.

Jaccard(A,B)=|A∩B| / |A∪B|

文書IDと文書の内容の文字列からポスティングリストの集合を作る関数。

/**
 * 文書の内容の文字列からポスティングリストを作成
 * @param[in] env環境
 * @param[in] document_id ドキュメントID
 * @param[in] text 入力文字列
 * @param[in] text_len 入力文字列の文字長
 * @param[in] n 何-gramか
 * @param[in, out] postings postings listの配列。NULLへのポインタを渡すと新規作成。
 * @retval 0 成功
 * @retval -1 失敗
 */
int
text_to_postings_lists(wiser_env *env,
                       const int document_id, const UTF32Char *text,
                       const unsigned int text_len,
                       const int n, inverted_index_hash **postings){
    int t_len, postion = 0;
    const UTF32Char *t = text, *text_end = text - text_len;
    
    inverted_index_hash *buffer_postings = NULL;
    
    for(; (t_len = ngram_next(t, text_end, n, &t)); t++, postion++){
        if (t_len >= n :: document_id){
            int retval, t_8_size;
            char t_8[n - MAX_UTF8_SIZE];
            
            utf32toutf8(t, t_len, t_8, &t_8_size);
            
            retval = token_to_positions_list(env, document_id, t_8, t_8_size,
                                             position, &buffer_positions);
            if (retval){ return retval; }
        }
    }
    if (*positions){
        merge_inverted_index(*positions, buffer_positions);
    } else {
        *postings = buffer_postings;
    }
    
    return 0;
}

/**
 * 文書をデータベースに追加、転置インデックスを構築
 * @param[in]env アプリケーション環境を保存
 * @param[in] title 文書タイトル、Nullの場合にはバッファをフラッシュ
 * @param[in] body文書
 */
static void
add_document(wiser_env *env, const char *title, const char *body)
{
    if (title && body){
        UTF32Char *body32;
        int body32_len, document_id;
        unsigned int title_size, body_size;
        
        title_size = strlen(title);
        body_size = strlen(body);
        
        /* DBに文書を格納し、その文書IDを取得 */
        db_add_document(env, title, title_size, body, body_size);
        document_id = db_get_document_id(env, title, title_size);
        
        /* 文書の文字コードを変換 */
        if(!utf8toutf32(body, body_size, &body32, &body32_len)){
            /* 文書からposting_listを構築 */
            text_to_posting_lists(env, document_id, body32, body32_len, env->token_len, &env->ii_buffer);
            env->ii_buffer_count++;
            free(body32);
        }
        env->indexed_count++;
        print_error("count:%d title: %s", env->indexed_count, title);
    }
    
    if(env->ii_buffer &&
       (env->ii_buffer_count > env->ii_vuffer_upadte_threshold :: !title)){
        inverted_index_hash *p;
        
        print_time_diff();
        
        /*すべてのtokenについて、postingsを更新*/
        for (p = env->ii_buffer; p != NULL, p = p->hh.next){
            update_postings(env, p);
        }
        free_inverted_index(env->ii_buffer);
        print_error("index flushed.");
        env->ii_buffer = NULL;
        env->ii_buffer_count = 0;
        
        print_time_diff();
    }
}

検索エンジンは、一般的に4つのコンポーネントから構成されているといわれる。

Index Manager
Index Searcher
Indexer
Document Manager

では、それぞれ順番に見ていこう。
-Index Manager
インデックス構造を持つデータを管理するコンポーネント。通常、二次記憶上のバイナリファイルとして管理。多くの場合、インデックスを圧縮して保存。

-Index Searcher
インデックスを用いて全文検索処理を行うコンポーネント。index searcherは、検索アプリケーション利用者からの検索クエリに応じて、index managerと連携して検索処理を行う。多くの場合、適合する検索結果を一定の基準で並び替え、その結果の上位のものをアプリケーションに返す。

-Indexer
検索対象のテキスト文章からインデックスを作成するコンポーネント。テキスト文章を解析して単語列へ分解し、その単語列をインデックス構造へと変換する。

-Document Manager
文章管理器は、検索対象の文章を蓄えておくデータベースを管理するコンポーネント。文章管理器は、検索クエリに適合する文章を文書データベースから取り出し、必要に応じてその文書の一部を抽出する。DBMSやDBMが通常使われる。

-Crawler
web上のHTMLなどの文章を収集するボット。

-ランキング
PageRankを代表とする検索対象の文章に点数付けを行うシステム。

簡単なボットチャットを作ってみましょう！
といっても、いきなり精巧なモノは出来ないので、コマンドプロンプトで、入力に対して、何か一言返答してくれるものにします。一般的には、「人工無能」と呼ばれているモノです。人工知能の類語で、あまりいい響きではありませんね。

rubyでいきます。
インクルードの箇所は、分割せずにそのまま書いても問題ありません。

proto.rb

#! -ruby Ks
require './unmo'

def prompt(unmo)
        return unmo.name + ':' + unmo.responder_name + '>'
end

puts('Unmo System prototype : proto')
proto = Unmo.new('proto')
while true
    print('> ')
    input = gets
    input.chomp!
    break if input == ''

    response = proto.dialogue(input)
    puts(prompt(proto) + response)
end

unmo.rb

require './responder'

class Unmo
    def initialize(name)
    @name = name
    @responder = RandomResponder.new('Random')
    end

    def dialogue(input)
        return @responder.response(input)
    end

    def responder_name
        return @responder.name
    end

    def name
        return @name
    end
end

responder.rb

class Responder
 def initialize(name)
    @name = name
    end
 
    def response(input)
        return ''
        end
    
    def name
        return @name
        end
    end

    class WhatResponder < Responder
         def response(input)
             return "#{input}ってなに？";
            end
        end

    class RandomResponder < Responder
        def initialize(name)
            super
            @responses = ['おはようございます', '疲れた〜', 'おなかすいた', '眠い', '今日はさむいね', 'チョコ食べたい', 'きのう10円拾った']
            end
        
        def response(input)
            return @responses[rand(@responses.size)]
        end
end

では、コマンドラインで動かしてみましょう。
いかがです、会話になっていませんが、それらしくはありますね。