カテゴリー

最新の記事

最近のコメント

最近のトラックバック

月別アーカイブ

ブログ検索

RSSフィード

ブロとも申請フォーム

この人とブロともになる

スポンサーサイト

スポンサー広告
--.--.--
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ベンチャーブログのランキングに参加しています。
下のバナーをクリックして応援していただけると嬉しいです。
にほんブログ村 ベンチャーブログへ

PHPとMySQLでツリー構造を扱う

PCとかネットとか
2008.06.07
 またしばらくご無沙汰しておりました。最近は仕事がボチボチ忙しいのもありますが、Webプログラミングで遊んだりもしていて、なかなか他の時間が取れません。で今回は、ちょっとしたプログラミングのネタです。

 いま取り組んでいるのは「あるコンテンツ群をカテゴリーで分類してWebブラウザーに表示する」というものです。どうせなら「自由度が高くて、カテゴリー構成を変更してもコンテンツの修正しないですむ仕組み」ということで、ツリー構造のカテゴリーにしたのですが、これがなかなか手強いヤツなのです。

 具体的なイメージがないと理解しにくいので、次のようなツリー構造のカテゴリーを考えてみましょう。カテゴリー名はいい加減なので、その部分では突っ込まないでください。階層構造を持つカテゴリーのサンプルです。

図1

 データは原則としてすべてMySQL、つまりRDBで管理することを前提とします。この場合、ツリー構造を最もシンプルに表現できるのは、次のようなデータ構造です。自分のID、親のID、自分のカテゴリー名という、3つのカラムを持つテーブルを定義すればいいわけです。

図2

 次にこのカテゴリーでコンテンツを分類するには、各コンテンツにカテゴリーID(category_id)を付与してあげればいい。そうしておけば、例えば「野球」に関係するコンテンツなら、
 

 SELECT コンテンツID FROM コンテンツテーブル WHERE カテゴリーID = '野球';


 といったSQL文を投げれば、検索できるわけです。(もちろん上のSQL文は考え方を示しただけなので、厳密には正しくありません。'野球'とあるのも、本当は'野球’というカテゴリー名を持つカテゴリーIDを記述すべきです)

 ここまで考えて「なかなかいい感じ~」と思っていたのですが、実はこの方法には大きな問題があります。'野球'で検索すると、'ジャイアンツ'や'タイガース'にカテゴライズされたコンテンツが、検索対象にならないのです。そりゃそうですよね。データベースには、ジャイアンツが野球のサブカテゴリーだということはわかりませんから。

 でもこのままでは困ります。例えば'スポーツ'でカテゴリー検索した人は、当然ながらスポーツのサブカテゴリーも含めた検索結果が欲しいわけです。サブカテゴリーも含めた検索を実行するプログラムを作らなければ「この役立たず!」と思われても仕方ありません。

 サブカテゴリーまで含んだ検索を実行するには、あるカテゴリーの下にどのようなサブカテゴリーがあるのか、リストアップする仕組みが必要です。実はこれがなかなか厄介な代物なのです。

 例えば'スポーツ'に含まれるサブカテゴリーを調べたい場合、すぐに次のSQL文を思いつくわけですが、これでは十分ではありません。

 SELECT カテゴリーID FROM カテゴリーテーブル WHERE 親のID = 'スポーツ';


 これではジャイアンツとタイガースが検索結果に含まれないのです。実はツリー構造のサブセットに含まれるすべての要素をリストアップするには、再帰的な処理が必要なんですね。

 ツリー構造は昔からあるものなので、当然ながらそれを扱うアルゴリズムもできあがっているはずです。そこでググッてみたのですが、なかなかきちんと説明したものが見あたらない。どうも「RDBでツリー構造を扱う」というのが、ひとつの壁みたいです。面白い方法を提唱している論文も見つかりましたが、あまり私の好みの方法ではありません。そこで自力で作ることにしたわけです。

 ここでプログラムの前提を示しておきます。

 まずカテゴリーテーブルは、MySQLの中に作成しておきます。テーブル作成のSQL文は以下の通りです。

create table category (
  category_id int not null auto_increment,
  parent_id int,
  category_name varchar(255),
  primary key(category_id)
);


 このテーブルの中に、先ほどと同じ構造のカテゴリー情報を作っておきます。

insert into category ( parent_id, category_name )
  values ( 0, "すべて" );
insert into category ( parent_id, category_name )
  values ( 1, "スポーツ" );
insert into category ( parent_id, category_name )
  values ( 2, "サッカー" );
insert into category ( parent_id, category_name )
  values ( 2, "ゴルフ" );
insert into category ( parent_id, category_name )
  values ( 1, "グルメ" );
insert into category ( parent_id, category_name )
  values ( 5, "レストラン(外食)" );
insert into category ( parent_id, category_name )
  values ( 5, "食品(中食)" );
insert into category ( parent_id, category_name )
  values ( 2, "野球" );
insert into category ( parent_id, category_name )
  values ( 5, "レシピ" );
insert into category ( parent_id, category_name )
  values ( 1, "エンターテイメント" );
insert into category ( parent_id, category_name )
  values ( 10, "音楽" );
insert into category ( parent_id, category_name )
  values ( 10, "映画" );
insert into category ( parent_id, category_name )
  values ( 2, "スキー" );
insert into category ( parent_id, category_name )
  values ( 10, "演劇" );
insert into category ( parent_id, category_name )
  values ( 10, "美術" );
insert into category ( parent_id, category_name )
  values ( 8, "ジャイアンツ" );
insert into category ( parent_id, category_name )
  values ( 8, "タイガース" );
insert into category ( parent_id, category_name )
  values ( 10, "テレビ・ラジオ" );


 insert文でcategory_idの指定をしていないのは、自動的にインクリメントした値を挿入するように、テーブル作成の時に定義しているからです。また後からカテゴリーが追加された場合をイメージして、インサートの順序をばらばらにしています。

 さてこのような構造のカテゴリーテーブルの中から、特定のカテゴリー以下のサブセットを抜き出すにはどうすればいいのでしょうか。私が今日、ガストで昼食を食べながら考えたのは次のようなものです。

図3

 そんなに難しいものではありません。あるカテゴリーのIDを指定して処理を呼び出すと、そのサブカテゴリーのリストが、直感的に理解できる順番で$indexに格納されます。おそらく同じアルゴリズムは、昔からあるはずです。(私が見つけられなかっただけ)

 実際のプログラムは以下の通りです。 (HTMLタグの部分を2バイト文字に置き換えてあるので、そのままコピペしても動きません。そうしないとブログの中でうまく表示されなかったので・・・)


<?php
require ( "config.php" );

$index = category_sub_list( $_GET['cat'] );
$value = array();
foreach ( $index as $value ){
  echo $value['name'] . " : " . $value['level'] . " <br>";
}

function category_sub_list( $id ){
  $ptr_i = 0;
  $ptr_s = 1;
  $stack = array();
  $index = array();

  $stack[$ptr_s]['id'] = $id;
  $stack[$ptr_s]['level'] = 0;
  $stack[$ptr_s]['name'] = '';

  $db = new mysqli ( DB_HOST, DB_USER, DB_PASSWORD, DB_NAME )
    or exit( "DB Connect Error..." );
  $stmt = $db->prepare( "select category_id, category_name from category
                           where parent_id = ?
                           order by category_id desc" )
    or exit( "DB Prepare Error..." );

  while ( $ptr_s > 0 ){
    $index[$ptr_i] = $stack[$ptr_s];
    $ptr_s = $ptr_s - 1;
    $stmt->bind_param( 'i', $index[$ptr_i]['id'] )
      or exit( "DB Parameter Bind Error..." );
    $stmt->execute()
      or exit( "DB Access Execute Error..." );
    $stmt->bind_result( $r_category_id, $r_category_name );
    while ( $stmt->fetch() ){
      $ptr_s = $ptr_s + 1;
      $stack[$ptr_s]['id'] = $r_category_id;
      $stack[$ptr_s]['name'] = $r_category_name;
      $stack[$ptr_s]['level'] = $index[$ptr_i]['level'] + 1;
    }
    $ptr_i = $ptr_i + 1;
  }
  $stmt->close();
  return $index;
}
?>


 この内容を「test.php」というファイル名で保存し、WebブラウザのURL入力の場所で「http://localhost/test.php?cat=○」(○にはカテゴリーIDを当てはめます)と記述すれば、サブカテゴリーのリストが、そのカテゴリーからの階層レベルの値と一緒に表示されます。例えば○に1を入れてアクセスすれば、下のように表示されるわけです。

図4

 とりあえずはこれで、制約のない階層構造のカテゴリーが扱えるようになりました。最近忘れっぽいので、ブログに残しておくことにします。そうそう、プログラム冒頭で呼び出しているconfig.phpですが、ここにはMySQLアクセスに必要な情報が、定数の形で定義されています。DB_HOST とか DB_USER、 DB_PASSWORD、DB_NAME がそれです。これらの情報はあまり公表したくないので秘密。皆さんの環境に合わせて、適当に決めてくださいね。
スポンサーサイト

ベンチャーブログのランキングに参加しています。
下のバナーをクリックして応援していただけると嬉しいです。
にほんブログ村 ベンチャーブログへ

FC2Ad

相続 会社設立

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。