N-gram

投稿した記事に関連する記事を自動で選択し、サイドバーを含む任意の位置に表示できる WordPress のプラグインであるSimilar Posts(Author: Rob Marsh, SJ) の設定の一例を紹介します。

ダウンロードとインストール

まず、下の二つのページからPost-Plugin LibraryとSimilar Postsをそれぞれダウンロードします。

• All Things Seen and Unseen » Post-Plugin Library
• All Things Seen and Unseen » Similar Posts

ダウンロードしたzipファイルから解凍されたフォルダをサーバのpluginフォルダにアップロードします。ブラウザからプラグイン管理ページを開き、Post-Plugin Library→Similar Postsの順にアクティベートします。

特徴

ソースを全て読んだわけではありませんが、このプラグインの特徴は、全記事からキーワードを抽出し関連度を算出し、DBの新たなテーブルに格納し直しているところだと考えます。その為、表示時間も早いですし、記事間の関連性を誘導する為に投稿者が記事に恣意的なカテゴリ・タグ付けをする必要がなくなる利点があります。ただし、設定によってはその機能を活かせなくなってしまう可能性があるので、以下に私の設定例を紹介します。

Similar Posts の設定の一例

General タブ

最初のおススメの設定項目は、

• Match the current post's category?
• Match the current post's tags?

の値をNoとすることです。YesやEvery tagにすると同一カテゴリ・タグのみから関連記事の推薦を行う設定となります。その為、タグやカテゴリを越えた横断的な推薦が出来なくなり、少しもったいないです。

Placement タブ

Output after post:

この項目をActivateにすると各記事の最後に関連記事を表示してくれます。
しかし、投稿本文と関連記事リストの間に広告を入れたい場合や表示位置を変えたい時があると思います。そういった場合はActivateせずにテンプレートの任意の場所に、

<?php similar_posts(); ?>

を挿入することでも、関連記事リストを表示することが出来ます。

Output in RSS feeds:

RSSフィードにも関連記事を表示する場合は、この項目のActivateをYESにしましょう。また、ここでParametersを初期設定で用いる場合はprefixの先頭にbrタグを追加しておきましょう。もしくは、strongタグを見出しタグ(h3やh4)に変えましょう。

というのも、もし記事の投稿の際に最後に改行を入れていない場合、strongタグの文字が本文の最終行に続けて連結されてRSSフィードに配信されます。なので、改行タグ（br）を挿入するか、見出しタグにしておいた方がちょっと見栄えが良いかと思います。もちろん、記事を投稿する際に毎度最後に空行を入れてもいいのですが、それは手間かな、と思います。

Other タブ

Relative importance of:

キーワードの重み付けの設定です。記事の本文、タイトル、タグそれぞれのキーワードの重要度を設定します。このブログの場合は、
content: 55%, title: 20%, tags: 25%
でかなりいい感じの推薦結果を得ることが出来ました。もちろん、この値は設置するブログのタイトルやタグ付けの方針によって変わってくると思いますので是非、試行錯誤してみてください。

Manage the Index タブ

日本語などマルチバイト文字を含むブログであれば、

• Handle extended characters?
• Treat as Chinese, Korean, or Japanese?

はYESにしましょう。

以上。こんな感じでしょうか。
今回はWordPressに関する初の記事となりましたが、↓の関連記事リストを見ると何だか頑張って関連していそうな記事を推薦してくれているように見えなくもないです（勿論、今後WordPress関連の記事を投稿すれば、この記事のリストも更新されます。

存外この推薦から新たな気づきが生まれることもあるので、とっても便利なプラグインです（「へー、その記事が関係するのか。共通点と相違点は何なんだろう？うーん、あ、確かに！」ってかんじで）。

余談ですが、DBのレコードを見たところ、どうやら本文からのキーワードの切り出しにはN-gram法が使われているようです。その為、文字コードがUTF-8であれば別途に形態素解析をしなくても、あらゆるマルチバイト言語の文章から機械的にキーワードマッチングできる単語(というよりN文字)集合を生成できるようです。勿論、単語の切り出し精度・速度は「N-gram」、「形態素解析」のどちらの方法にも一長一短ありますけれど。

作者のRob Marsh, SJさんスゴイなぁ。

今回実装したことは、

• IndexRecordクラスにフィールド更新用のメソッドやハッシュフィールドを追加（今後改善の必要大）。
• 検索語を含んでいるファイルをピックアップする（色々と無駄な部分あり）。

辺りです。

後述に現在の問題点とその解決案を考えてみましたが、先ずはソースコードと実行結果(デバッグプリント)を示します。

追記：こちらに→ 検索エンジンを実装 (4)AND演算 - Yukun's Blog 完成版を書きましたので、そちらをご覧ください。↓以下、黒歴史(>_<)↓

IndexRecord.java

import java.util.ArrayList;
import java.util.TreeMap;

public class IndexRecord {
  // 総出現回数
  Integer count;
  // 出現したファイルID
  ArrayList<integer> file_ids;
  // ファイル内の出現位置(ファイルの先頭からのオフセット)
  ArrayList<integer> word_poses;
  // ファイルIDごとに出現数をカウント<ファイルid, 出現数>
  TreeMap<integer, Integer> idcntMap;

  private IndexRecord() {}
  public IndexRecord(int id, int pos) {
    count = 1;
    file_ids = new ArrayList<integer>();
    file_ids.add(id);
    word_poses = new ArrayList<integer>();
    word_poses.add(pos);
    idcntMap = new TreeMap<integer, Integer>();
    idcntMap.put(id, 1);
  }

  public void renewal(int id, int pos) {
    count++;
    file_ids.add(id);
    word_poses.add(pos);

    if(idcntMap.containsKey(id)){
      Integer idcnt = idcntMap.get(id);
      idcnt++;
      idcntMap.put(id, idcnt);
    } else {
      idcntMap.put(id, 1);
    }
  }

  public String toString() {
    StringBuffer sb = new StringBuffer();
    sb.append(count);
    for(int i = 0; i < file_ids.size(); i++){
      sb.append(" (" + file_ids.get(i) + ", " + word_poses.get(i) + ")");
    }
    sb.append(" "+ idcntMap);
    return sb.toString();
  }
}

Make2Gram.java

import java.io.File;
import java.io.FileReader;
import java.io.BufferedReader;
import java.io.IOException;

import java.util.ArrayList;
import java.util.TreeMap;

public class Make2Gram{
  public static final boolean DEBUG = true; // デバッグ用フラグ
  public static void main(String[] args) throws IOException{
    if(args.length == 0){
      System.out.println("引数にディレクトリ名を指定してください");
      System.exit(1);
    }
    int N = 2; // bigram

    // http://sattontanabe.blog86.fc2.com/blog-entry-55.html
    // Java 再帰的にファイルを検索 ／ Chat&Messenger
    // のクラスFileSearchを使用しています
    FileSearch search = new FileSearch();
    File[] files = search.listFiles(args[0], null); // 全てのファイルを取得
    // ファイルIDとパスの対応表
    TreeMap<integer, File> fileMap = new TreeMap<integer, File>();
    ArrayList<string> docs = new ArrayList<string>();

    for(int i=0; i < files.length; i++){
      fileMap.put(i, files[i].getAbsoluteFile());
      BufferedReader br = new BufferedReader(new FileReader(files[i]));
      StringBuilder sb = new StringBuilder();
      String line;
      while((line = br.readLine()) != null)
        sb.append(line);
      br.close(); // ファイル内容(RAW)を格納
      String text = sb.toString(); // ファイルの内容 改行抜き
      docs.add(text);
    }

    //テキストの部分文字列とそのIndexRecordクラスを関連付けるMap
    //TreeMapなのでMapのキーにした部分文字列でソートされる
    TreeMap<string, IndexRecord> gramMap = new TreeMap<string, IndexRecord>();
    for(int i = 0; i < fileMap.size(); i++){
      // ファイルごとの処理
      String text = docs.get(i);
      for(int j = 0; j < text.length() - N; j++){
        //テキストからN文字取り出す
        String gram = text.substring(j, j + N);
        if(gramMap.containsKey(gram)){
          //gramMapに登録されてる文字列ならカウント等を増やす
          IndexRecord ir = gramMap.get(gram);
          ir.renewal(i, j);
          gramMap.put(gram, ir);
        }else{
          //gramMapに登録されていない文字列なら登録
          gramMap.put(gram, new IndexRecord(i, j));
        }
      }
    }

    //for(String part : gramMap.keySet())
      //System.out.printf("%s : %sn", part, gramMap.get(part));
    String input = "N文字"; // 検索語(e.g.)
    if(DEBUG) System.out.println("input #=> "+ input);
    String[] swords = new String[(input.length()+1)/2];
    boolean odd = false; // 文字列長の偶奇判定
    if (input.length() < 2){
      System.out.println("2文字未満の処理は未実装");
      System.exit(1);
    }
    // 検索文字列をN文字単位に分割
    for(int i = 0, j = 0; i < input.length()-N; i += N, j++){
      swords[j] = input.substring(i, i+N);
    }
    if ((input.length() & 1) == 1){ // 文字列長が奇数
      swords[swords.length-1] = input.substring(input.length()-N, input.length());
      odd = true;
    }
    if(DEBUG){
      System.out.print("swords #=> ");
      for(String part : swords) System.out.print(part +" ");
      System.out.println();
    } // [N文, 文字](e.g.)
    TreeMap<integer, Integer> id_per_cnt = new TreeMap<integer, Integer>();
    // N文字単位のIndexRecordを格納する配列
    IndexRecord[] ng_records = new IndexRecord[swords.length];
    // 2文字ごとにgramMapと照合
    for(int i = 0; i < swords.length; i++){
      if(!gramMap.containsKey(swords[i])) {
        System.out.println("  検索語：【"+ input +"】はありません。");
        System.exit(1);
      }
      IndexRecord ir = gramMap.get(swords[i]);
      ng_records[i] = ir;
      TreeMap<integer, Integer> _idcntMap = ir.idcntMap;
      for(Integer id : _idcntMap.keySet()){
        if(id_per_cnt.containsKey(id)){
          int cnt = id_per_cnt.get(id);
          cnt += _idcntMap.get(id);
          id_per_cnt.put(id, cnt);
        } else {
          id_per_cnt.put(id, _idcntMap.get(id));
        }
      }
      if(DEBUG) System.out.println("  "+ swords[i] +"："+ ng_records[i]);
    }
    if(DEBUG) System.out.println("id_per_cnt #=> "+ id_per_cnt);

    for(Integer id : id_per_cnt.keySet()){
      // ↓以下の部分の評価は中途段階。出現位置を考慮に入れた判定に変更予定。
      // それに伴い、IndexRecordのデータ構造は要変更。
      if(id_per_cnt.get(id) / swords.length > 0){
        if(DEBUG) System.out.println("  検索語はファイルid["+ id +"]中に存在する可能性あり。");
        String target_doc = docs.get(id);
        int pos = target_doc.indexOf(input);
        String mch = target_doc.substring(pos, pos + input.length());
        System.out.println("  照合文字列 : "+ mch);
      }
    }
  }
}

実行結果(コマンドライン引数部分は省略)

input #=> N文字
swords #=> N文 文字
  N文：2 (0, 1) (0, 42) {0=2}
  文字：3 (0, 2) (0, 43) (1, 61) {0=2, 1=1}
id_per_cnt #=> {0=4, 1=1}
  検索語はファイルid[0]中に存在する可能性あり。
  照合文字列 : N文字

現在の問題点

IndexRecordクラス:ArrayList型ではフィールド(ファイルidと出現位置)の関係性を取りづらい。

解決案

IndexRecordクラスのフィールドにファイルidを主キーとして、その部分単語の全ての出現位置を求められるハッシュデータが必要かと考えました。

今回もうすうすは感じていましたが、データ構造を設計し間違えるとプログラム構造が煩雑になりやすいです。初めから仕様を明確にしておけばデータモデリングでミスることもなかったかな。

しばらくは、今後の実装機能の洗い出しとそれに対応できるクラス構造を考えてみようかな。また、N-gramに分割する処理部分は別クラスのインスタンスメソッドとしてまとめたほうが良いですね。並行してデザインパターンも復習しておこう。

id:d-kamiさんから改良版Make2Gram付きトラックバックを頂きました(連絡方法がわからんのでトラックバックで - マイペースなプログラミング日記)(はてなダイヤリーから移転前)。d-kamiさん、ありがとうございます。

上記のページにあるコードから、TreeMapやsubstringを用いたbigramの切り出し・カウント方法などを学ばせて頂きました。

さて、今回の実装その2は以下の機能を加えました。

1. コマンドライン引数にディレクトリ名を指定して、そのディレクトリ以下のファイル全てを処理の対象とする。
2. N-gram情報には文書IDと部分文字列の出現位置を格納するようにデータ構造の拡張。

Continue reading

今回はN-gramでテキストを分解します。N-gram法とは対象の文字列を一定のN文字単位で分解し、それの出現頻度を求める方法です。これによって、検索エンジンに使われる転置インデックスを作成したいと思います。転置インデックスの作成方法にはN-gramの他に形態素解析があります。両者の性能の長短は全文検索 - Wikipediaに詳しく載っています。

Javaソースコード(Make2gram.java)

さて、まずは文字列を2単語に切り分けるプログラムを作成しました。データ構造は単純にArrayListで、出現頻度も求めていません。

import java.io.*;
import java.util.*;
/**
 * N-gram法
 */
public class Make2gram {
  public static void main(String[] args) {
    final short nsepa = 1; // 2gram
    String line;
    ArrayList<stringBuffer> filelist = new ArrayList<stringBuffer>();
    ArrayList<stringBuffer> bigram = new ArrayList<stringBuffer>();

    if (args.length < 1) { // コマンドライン引数の数
      System.out.println("How to use: java Make2gram [filename]");
      System.exit(1);
    }
    try {
      BufferedReader br = new BufferedReader(new FileReader(args[0]));
      while ((line = br.readLine()) != null) {
        //System.out.println(line);
        filelist.add(new StringBuffer(line)); // 入力ファイルは一行=一要素として格納
      }
      br.close();
    }
    catch (Exception e) {
      System.err.println("[main] : " + e.toString());
    }
    for (Iterator it = filelist.iterator(); it.hasNext(); ) {
      StringBuffer str = (StringBuffer) it.next();
      int lm = str.length() - nsepa;
      for (int i = 0; i < lm; i++) {
        StringBuffer bi = new StringBuffer(4); // 4Byte(2文字)分の容量(Javaの内部文字コードはUnicode)
        bi.append(str.charAt(i)); // append():文字列の末尾に追加
        bi.append(str.charAt(i+1));
        bigram.add(bi);
        //System.out.print(str.charAt(i));
        //System.out.println(str.charAt(i+1));
      }
    }
    // 2-gramを表示
    for (Iterator it = bigram.iterator(); it.hasNext(); ) {
      System.out.println(it.next());
    }
  }
}

入力ファイル(text.txt)

検索された文書は「更新順」「ファイル名順」「文書のタイトル順」などにソートされる。
一般的な検索エンジンでは独自のランク付けルールも適用し「重要度」などと呼んでいるものもある。

実行結果

検索
索さ
され
れた
た文
文書
書は
は「
「更
更新
新順
順」
」「

…＜省略＞…