このページは福井県立大学の田中求之が2006年1月まで運用していた Mac のサーバ運用に関する会議室 「Web Scripter's Meeting」の記録です。情報が古くなっている可能性がありますのでご注意ください。

条件近似検索方法について

発言者:石津@RJC
( Date Friday, July 19, 1996 17:45:35 )


すいません、どうしても自分で組めないScriptについて教えてください。

現在、複数の条件を設定しておいて、ユーザーがいくつか条件を選択した場合に
近似した条件のレコードのURLをリストして返すというスクリプトを組みたいと
思っています。

条件は5つのカテゴリーで各カテゴリー毎に5-8ぐらいの項目があります。
(トータルで最大40項目ぐらいになります)

チェックボックスもしくはラジオボタンによる複数条件の選択の結果、その条件
にできるだけ近い(まったくイコールだけなら簡単なんですが...)条件を選択
する方法にはどういうものがあるのでしょうか?

例えば40の条件のうち10コが必要というように選択されたら、その10コの条件を
含む、もしくは10コには満たないけれど8コなら満たす条件のレコードを選択し
リストしたいのです。

AppleScriptで記述するやり方であるようでしたら教えてください。

田中求之 さんからのコメント
( Friday, July 19, 1996 18:51:25 )

検索を行うソフトは何ですか? ソフトではなく、ファイルの内容の検索でしょうか?

>例えば40の条件のうち10コが必要というように選択されたら、その10コの条件を
>含む、もしくは10コには満たないけれど8コなら満たす条件のレコードを選択し
>リストしたいのです。

この場合、10個の条件に優先順位はありますか? もし優先順位がついているので
あれば、

・10個の条件の AND 検索を行う
・もし該当がなければ優先順位の一番低いものを外して9個の条件で AND 検索を行う
・もし該当がなければ優先順位の次に低いものを外して8個の条件で AND 検索を行う
 …(該当するものが見つかるまで行っていく)

という方法は考えられますよね。ただし、処理時間がけっこう長くなってしまう
可能性が高いですが(特に AppleScript でこなす比重が多い場合)。



石津@RJC さんからのコメント
( Saturday, July 20, 1996 00:58:25 )

早速のコメントありがとうございます。
したいのはWebStarからのcgi機能として実装したいのです。
htmlで書いたフォームから必要条件をチェックしてもらい、それに該当する
条件のhtmlファイルを100件ぐらいの中から検索して、該当(もしくは近似)
条件のファイルのURLをリストするというものです。

できればAplleScriptのcgiだけで実装したいのですが、不可能ならばFileMaker
なら用意できる状況です。
条件そのものは優先順位はつけないですませます。
また10コというような条件選択の限定もしたくないのですが、やはりそれは
よくばりでしょうかね...。

石津@RJC さんからのコメント
( Saturday, July 20, 1996 01:12:53 )

今現在考えているのは、条件をカテゴリ毎に該当するかどうかを予め
各htmlファイルに記述しておいて、それをフォームから入力されたものと
突き合わせて調べるという方法です。

例えば
10110100-00010101-11110010-11011011-11011110
というように40コの条件に該当すれば1、該当しない場合には0を代入した
値をカテゴリ毎に"-"で分けて記載しておきます。

FORMではユーザが必要条件をYesにすると1、NOにすると0を入力するように
作成しておき、POSTすると
00000000-1000100-11011000-11100000-00110100
という文字列を作成するようにしておきます。

この文字列を順番に比較して合致した件数が多い順にリストするという
ものです。しかし、私にはどうやってScript書いてよいか判りませんでした。
勉強不足ですね...。(;_;)

この8bitコードみたいな文字列をASCII numberに直して+-2の数字の該当
ファイルをひっぱるというのも考えましたが、これは近似にはならない
ので失敗でした。

うーん、何か考える方法が違っていますでしょうか?

田中求之 さんからのコメント
( Saturday, July 20, 1996 03:50:23 )

あらかじめ HTML ファイルに条件(というか検索の際の index に該当する情報)
を埋め込んでおけるなら、検索自体はかなり速度があげられますね。内容をすべて
検索するなんてことをやっていたら、少なくともこの会議室の検索程度には
時間がかかってしまいますから (^_^;;  (180以上のページを検索している
わりには早いのではないかと、ひそかに思ってたりしますが)

石津さんの考えられた、条件を 1/0 で表しておいてチェックを行うのは、
速度を別にすれば簡単ですね。

FORM から入力された条件を 000100101010100... のように、ハイフンで区切らずに
0/1 で並べておきます。ページの方にも同様に

<!--index:010100000...001-->

のように、コメントタグで条件を埋め込んでおくようにします。このページに埋め込まれ
た条件は

item 1 of 
pickupFrom file tgPage startOf "<!--index:" endOf "-->" with Trim

で取り出せます(Tanaka's osax)。

あとは、

set hitPoints to 0
repeat with x from 1 to 40
  if char 1 of formKey = char 1 of paegeKey then set hitPoints to hitPoints +1
end repeat

(formKey がユーザーが入力した条件、pageKey がページの条件)

で、一致する度合いを 0〜40の点数で表せますので、点数の高いものから選べばいい
わけです。

また、一致しなくても気にしない条件には * を入れておき、このときには無条件に
hitpointsを加算するといったことも可能ですね。

問題は、どこまで使いものになる速度が出るか、ですけど。

石津@RJC さんからのコメント
( Sunday, July 21, 1996 01:04:29 )

田中さん、どうもありがとうございます。
早速試してみます。

速度面ではこの条件と該当ファイルの組み合わせを列記したindexファイルを
作成しておいて、これを検索させ、そこからリストを作って該当ファイルに
ジャンプできるようにすれば、いくらかは改善できそうですね。

出来るかどうかわかりませんが、チャレンジしてみます。

石津@RJC さんからのコメント
( Monday, July 22, 1996 14:07:20 )

ということで4時間半ほどトライしてみました。
結果はCan't make some data into the expected type. の嵐で、一度も
成功していません。(;_;)

取り敢えず条件をまとめてURLと一緒に記述したlistindexというファイルを
作り、FORMから入力されたものと「合致」するケースについては、レコード
をリストしてURLへジャンプさせることはできたのですが、肝心の近似検索
のために教えていただいた方法を組み込むことがうまくできません。

listindexには条件、会社名、URLという順でtab区切りで記述しております。

これをreadFromFileでいったん読み込み、itemsToListでリストし、この一番
はじめのアイテムをpageKeyとして定義します。

そこからrepeatへ持ち込むようにしているのですが、ここが大間違いしている
ようです。(推測)すいませんがScriptを引用しますので間違いを指摘してい
ただけないでしょうか?試行錯誤途中なのでいろいろとヘンな部分はあるかと
思いますが...。

一応file_db_1のスクリプトを参考にしています。
下のほうのページ表示部分をバッサリ切っていろいろと検証してみましたが
どうしてもエラーになるので上で失敗しているのだと思っています。
---------------------------------------------------------------------

property crlf : (ASCII character 13) & (ASCII character 10)
property LF : (ASCII character 10)

property http_10_header : "HTTP/1.0 200 OK" & crlf & "Server: WebSTAR/1.0 ID/ACGI" & crlf & ツ
  "MIME-Version: 1.0" & crlf & "Content-type: text/html" & crlf & crlf

property redirect_header : "HTTP/1.0 302 Found" & crlf & "Server: WebSTAR/1.0 ID/ACGI" & crlf & ツ
  "MIME-Version: 1.0" & crlf & "Location: "

property thisFldr : ""
property bodyPath : ""

---- 起動時に、この CGI の入っているフォルダーのパスを
---- thisFldr プロパティにセットする
---- 同時に、検索するファイルのパスを bodyPath にセットする

on run
  set myPath to path to me
  tell application "Finder"
    set thisFldr to (folder of myPath) as string
  end tell
  set bodyPath to thisFldr & "listindex"
end run

on idle
  return (60 * 60 * 24)
end idle

on ヌevent WWWスsdocネ path_args ツ
  given ヌclass kforネ:http_search_args, ヌclass postネ:post_args
  try
    --- post_args のデコード
    set myList to DecodeJArgs post_args
    
    --- 受け取ったメッセージを整理する
    set formKey to (item 1 of myList) & (item 2 of myList) & (item 3 of myList) & (item 4 of myList) & (item 5 of myList) ツ
      & (item 6 of myList) & (item 7 of myList) & (item 8 of myList) & (item 9 of myList) & (item 10 of myList)
    
    --- 抜き出した検索キーを元にファイルを検索し、該当語句の見つかった
    --- 行をリストにする
    set myList2 to readFromFile bodyPath
    set myList2 to itemsToList myList2
    set pageKey to item 1 of myList2
    
    repeat with pKey in myList2
      set hitPoints to 0
      repeat with x from 1 to 40
        if character 1 of formKey = character 1 of pageKey then set hitPoints to hitPoints + 1
      end repeat
      set myList3 to myList2 ツ
        & hitPoints & pageKey & (item 2 of myList2) & (item3 on myList2)
    end repeat
    
    ---
    if myList3 ュ {} then
      --- 表示用にデータを加工する
      set myNM to count items of myList3
      set myData to "<h3>" & (myNM as string) & "件のデータが見つかりました</H3>" & return & return
      repeat with thisL in myList3
        set myTem to itemsToList thisL
        set myData to myData ツ
          & "<b><A HREF=\"" & (item 3 of myTem) & "\"" & (item 2 of myTem) & "</A>" & return
      end repeat
    else
      set myData to "<h3>該当するデータはありませんでした</h3>"
    end if
    
    return http_10_header & "<TITLE>検索結果</TITLE>" & crlf ツ
      & "<H2>検索結果</H2><HR>" & crlf ツ
      & "<pre>" & myData & "</pre>" & crlf ツ
      & "<HR><P><i>File Search powered by Tanaka's osax</i>"
    
  on error errMsg number errNb
    
    return http_10_header & crlf ツ
      & "<TITLE>Error</TITLE>" & crlf ツ
      & "<h1>Error</h1>" & crlf ツ
      & "<h3>処理中にエラーが生じました</h3><HR><P>" & errMsg
  end try
  
end ヌevent WWWスsdocネ

田中求之 さんからのコメント
( Monday, July 22, 1996 14:41:40 )

set FormKey ...  の部分で、FORM による入力をまとめているようですが、FORM
からのデータ(Value)は 1/0 になるようになっているんですよね? つまり、

FormKey = "0010110011"

PageKey = "1010110001"

というように、どちらも1/0が10個並んだ文字列になることは確かですか?

この部分のデータの型がずれていると、チェックはうまくいかないのですが。
逆に言うと、この部分さえちゃんとできているなら、問題はないはずなんです
けどね。

私の方でも試してみます。

石津@RJC さんからのコメント
( Monday, July 22, 1996 15:20:41 )

>というように、どちらも1/0が10個並んだ文字列になることは確かですか?

お手数をおかけいたします。
データの形式については問題ないと思います。
この部分は近似検索でなく合致検索を行う場合には正常に動作しております。

私は(自分で)repeatのハンドリングがイマイチ理解できていないので、そこ
に問題があるのかなと思っているのですが...。

またヒットポイント順にsortする方法がわからなかったので、これも入れて
いません。(AppleScriptミニミニリファレンスにはFinderを経由する方法
しかなかったのですが、他のコマンドがあるのでしょうか?)

田中求之 さんからのコメント
( Monday, July 22, 1996 16:17:52 )

スクリプトを拝見していて、気になったところがあります。

===
    repeat with pKey in myList2
      set hitPoints to 0
      repeat with x from 1 to 40
        if character 1 of formKey = character 1 of pageKey then set hitPoints to hitPoints + 1
      end repeat
      set myList3 to myList2 ツ
        & hitPoints & pageKey & (item 2 of myList2) & (item3 on myList2)
    end repeat
===

hitPoints を計算している部分ですが、おそらくこれは、このままでは動かない
はずです。これについては、あらためコメントしますが、ここの部分が問題でしょう。

石津@RJC さんからのコメント
( Tuesday, July 23, 1996 01:00:53 )

やはりそうですか。
自分でも一番怪しいと思ってました。
すいません、ご教授ください。

田中求之 さんからのコメント
( Tuesday, July 23, 1996 19:24:42 )

まず、ファイルについて確認しておきます。

listindex は、各行に条件、会社名、URLがタブ区切りで並んでいるわけですね?
そして、この条件が 1/0 の文字が10個並んだものになっているというわけで
すね?

そして、FORM ページから受け取ったメッセージをデコードした結果であるformKeyも
同じく 1/0 の文字が10個並んでいる。

この場合、listindex に載っている各 URL の HitsPoint のだし方は、以下のように
なるはずです。

set myList2 to readFromFile bodyPath
set AppleScript's text item delimiters to {return}
set myList2 to text items of myList2

set myList3 to {}

repeat with thisURL in myList2
  set thisURL to contents of thisURL
  set thisURLList to itemsToList thisURL
  set targetIndex to item 1 of thisURLList
  set hitPoint to 0
  repeat with x from 1 to 10
    if character 1 of targetIndex = character 1 of formKey then
      set hitPoint to hitPoint +1
    end if
  end repeat

  set end of myList3 to (hitPoint as string) & tab & (item 2 of thisURLList) & tab & (item 3 of thisURLList)

end repeat

set myList3 to myList3 as string
set AppleScript's text item delimiters to {""}

この時点で、myList3 には、各行に、ヒットポイント・企業名・URL がタブ区切りで
並んだものになります(テキストデータです)。ですので、これを何らかのツールなど
でソートを行って HitPoint の高い順番に並び替えて、あとは myList3 を元に
表示用のページを生成していくことになります。

もしソートを行う適当なツールがない場合には、上の repeat 処理の中で

  set end of myList3 to (hitPoint as string) & tab & (item 2 of thisURLList) & tab & (item 3 of thisURLList)

の部分を

  if hitPoint > 6 then
    set end of myList3 to (hitPoint as string) & tab & (item 2 of thisURLList) & tab & (item 3 of thisURLList)
  end if

とやっておけば、HitPoint が7以上のものを抜き出せます。このように、HitPoint の
計算を行う部分で、あらかじめ選別を行っておき、さらに、ユーザーに表示するページで
HitPoint も表示すればよいと思います。


なお、スクリプトは、コメント覧に直接書き下したものですので(実際に試したものでは
ないので)、もしかしたらこのままでは動かないかもしれませんが、基本的な処理の手順は
間違っていないと思います。

参考になれば幸いです。

石津@RJC さんからのコメント
( Thursday, July 25, 1996 18:18:17 )

レスが遅くなってすいませんでした。
今週はInteropでたいへんだったもので...。

早速明日試してみたいと思います。
こうした近似検索は結構ニーズがあると思いますので、方式が確立できたら
スクリプトは公開させていただきたいと思います。
どうもありがとうございました。

石津@RJC さんからのコメント
( Friday, July 26, 1996 17:40:58 )

ということでまた2時間ほど格闘してみました。
が...Can't make some data into the expected type.になってしまいます。

田中さんの確認された条件に間違いはなく、Scriptの構文チェックも問題は
なかったのですが、なぜか.....。
リファレンスを確認しながら再度チャレンジしてみようと思います。

田中求之 さんからのコメント
( Friday, July 26, 1996 19:01:39 )

乗りかかった船というか、なんというか、気になるので、よかったら
サンプル用のページ( Index と FORM )を送ってもらえますか?
私の方でも試してみますけど。

もっとも、部外秘のデータが載っている等であれば結構ですが。


石津@RJC さんからのコメント
( Sunday, July 28, 1996 01:08:38 )

テスト用データでやってますのでお送りするのは問題ないです。
でもお手間になってしまって申し訳ありません。

月曜日に会社から送らせていただきます。

石津@RJC さんからのコメント
( Monday, July 29, 1996 16:12:55 )

本日メール送らせていただきました。:-)

それはそれとして、私も今日更に3時間ほどアプローチを変えて試してみま
した。今回は同じ条件ファイル(indexlist)を利用して条件の何ケタ目に
注目して、該当するかどうかを調べるというものです。

例えば0101000...という10コの条件の8コ目が1のものをリストする、という
ようなものです。これだともっと楽にできそうかな...と思ったのですが、
残念ながらこちらもCan't make some data into the expected type.となって
しまい、どうしても成功しません...。

ということで、今私はindexlistをreadFromFileしてからの扱い方に問題が
あるのではないかと思い、その辺を重点に試行錯誤をしてみています。

毎日ブチブチ言いながら仕事しているので、そろそろ周りから心配されるよう
になってしまいました。:-)
Scriptはなかなか大変ですね....。

田中求之 さんからのコメント
( Monday, July 29, 1996 16:38:51 )

受け取ったデータを元に Index チェックを行うスクリプトの
サンプルをお送りしておきました。お試しください。

お役にたてばよいですが。

石津@RJC さんからのコメント
( Monday, July 29, 1996 20:33:03 )

田中さん、どうも本当にありがとうございました。
早速試してみましたので結果の報告です。
動作するよう作っていただいたので、動作そのものの報告は良しとして...

条件を40コ、データを100コにして試してみたところ見事タイムアウトに
なりました。(;_;)ちなみにマシンは7600/120です。
そこでデータを75コにしたところ、この量なら45秒で検索結果が返って
くることが分かりました。
40のデータ項目を75件とそれぞれ突き合わせての結果なので、これぐらい
かかってしまうものでしょうか。

ということで条件を減らすのと、データを減らすのとよりパワーのあるマ
シンを使うのとで、使用条件のチューニングをしてみようと思います。
速くAppleScriptのPPCナイティブが出てくれないかな...。

あ、そうそうcgiは必ずFinderで一番手前にしておかないとタイムアウトに
なってしまいます。バックグラウンドでは処理が遅くなるので駄目見たい
ですね。

このスクリプトはいくつかの条件を実験した上で田中さんから公開していた
だくようにしましょう。少ない条件なら十分実用になりそうです。

本当にありがとうござました。

石津@RJC さんからのコメント
( Monday, July 29, 1996 21:01:28 )

条件を少なくして実験計測したところ20コだとデータ75件の検索で
25秒で結果が返ります。
およそ10コの条件追加で10秒検索に余計な時間がかかることになります。
(ただし604/120のCPUの場合で、です)
10コの条件を100データぐらいがちょっと遅くても妥当なセンかな、という
ところでしょうか。

ちなみに『どちらでもいい』項目をScriptから削っても速度には影響しませ
んでした。このScriptでreadFromFileの代わりに予め特定のファイルのデータ
をキャッシュしておくような方法は取れないものでしょうか?

石津@RJC さんからのコメント
( Monday, July 29, 1996 21:17:41 )

ちなみに上の検索時間はMacHTTP2.2で実験したものです。
今Boulvardで実験したら(20条件75データ)バックグラウンドで21秒、
フォアグラウンドで12秒!でした。
サーバによってこんなに違いがあるもんなんですね。
WebStarの実験は明日やってみたいと思います。

田中求之 さんからのコメント
( Monday, July 29, 1996 22:25:44 )

>サーバによってこんなに違いがあるもんなんですね。

はっきりいって、相当に違います。というか、ぶっちゃけた話、MacHTTP で CGI を
動かすと遅いんです。CGI を一番手前に持ってきてないと、タイムアウトが多くなり
ます。

WebSTAR をはじめとして、最近のものは、Thread-Manger に対応したことによって
サーバーが他のアプリケーションに与える影響が少なくなっています。このため、 CGI
も比較的高速で動きます(私のサーバーが、この会議室を含めたすべての処理をたった
一つの CGI にまとめておけるのも WebSTAR で運用しているからです)。

>このScriptでreadFromFileの代わりに予め特定のファイルのデータ
>をキャッシュしておくような方法は取れないものでしょうか?

property に Indexdata を作って、CGI の起動時にファイルを読み込んでおくよう
にすればよいでしょう。

しかし、ファイルの読み込みにはそれほど時間がかかりませんよ。Indexsearch の速度
を上げたいと思ったら、やはり、キーになっている Index の比較処理を高速化する
しかありません。最終的には osax にするしかないかもしれませんね。

石津@RJC さんからのコメント
( Tuesday, July 30, 1996 00:37:43 )

やはりスレッドマネージャの効果は絶大なんですね。
正式な運用ではWebStarとの組み合わせとなるので、まず大丈夫そうかな。
取り敢えず測定はしてみますね。

石津@RJC さんからのコメント
( Tuesday, July 30, 1996 13:16:07 )

ということで実測してみました。
結果一番CGIの処理が速かったのはBoulevard,Webstar,WebCenter,MacHTTPの
順でした。Boulevardにはcgiに関して結構大きいバグがありますが、キャッ
シュ機能などが効いているのか一番速く結果が返ってきました。
40条件を100データでCGIをフォアグラウンドにして実験した結果です。
平均して速い順に30秒32秒45秒55秒という感じでした。
WebCenterは調整が可能なので一番速かった設定での実験です。

石津@RJC さんからのコメント
( Tuesday, July 30, 1996 16:24:32 )

WebCenterではcgiがバックグラウンドにある方が動作が速いという結果が
出ました。

10条件を100データ、cgiをバックグラウンドにした場合とフォアに
した場合で比較すると15秒対17秒で、cgiをバックにした方が応答が返るまで
の時間が短いという不思議な結果が出ました。

なんだか良く分からないけど、これはこれで便利かも。