美しく、素晴らしい体験を提供しよう。検索エンジン「Draw」開発チーム。

watashida

https://scratch.mit.edu/projects/302147437/
とりあえずwikipediaから200個ほど持ってきました。
かなり重いです。
リストの要素が長すぎるときに全文表示されないのでそこも何とかしたほうがいいかもです。

検索アルゴリズムの問題なのか「共和国」とかで調べてもDrawのページが一番上にくるのも気になります。

kakurenbo

watashida wrote:
https://scratch.mit.edu/projects/302147437/
とりあえずwikipediaから200個ほど持ってきました。
かなり重いです。
リストの要素が長すぎるときに全文表示されないのでそこも何とかしたほうがいいかもです。

検索アルゴリズムの問題なのか「共和国」とかで調べてもDrawのページが一番上にくるのも気になります。

僕も、半分勘で組んだので、おかしいかもです。
編集距離が0.6以上にならないのも気になります。勘違いでした。

Last edited by kakurenbo (April 12, 2019 12:15:00)

gagagagagagagaqqww

とりあえずページ切り替え

ARATAKU

そもそも、大量の候補の中から、曖昧検索をかける必要が無いような気がしてきました。
なぜなら、「アメリカ合衆国」を検索しようとして、「アメリカン合唱国」のように計算する人などいないからです。
見出しみたいな部分にだけ曖昧検索をかけて、google検索のように、「もしかして〇〇」のように出来るようにすれば良いと思います。
（見出し以外のところまで曖昧検索をかけていては、時間がかかって仕方が無いです。）

kakurenbo

そう言えば、編集距離算出アルゴリズムをwatashidaさんのに置き換えましたが、
片仮名平仮名の変換は行ってません。

gagagagagagagaqqww

全データを検索していてはきりがないので、39データくらいで切り上げることにしません？のこりは「もっと見る」的なコマンドを用意すれば…

watashida

検索アルゴリズムの問題なのか「共和国」とかで調べてもDrawのページが一番上にくるのも気になります。

原因特定しました。
関数「候補を(文字列)に近い順に並べ替える。」の下から4つ目のブロック
「(レーベンmem) / ((count4) + 4) を近似度に追加する」を「(レーベンmem) を近似度に追加する」にしてください。

あと実験してての改良案です。

1.
現在以下の理由で最小値を評価に入れていますが、

例えば①「scratch, javascript」と②「scream, school」でscratchに近いほうを選ぶとき、それぞれの距離が「0, 10」「4, 4」であるとします。
もし足し算で評価していれば0 + 10 > 4 + 4となるので②が選ばれるはずです。しかし、雰囲気的にはscratchと完全に一致している方が距離が近い気がします。ここで最小値を用いると完全に一致しているものが優先で選ばれます。これだと直感通り0 < 4で①が選ばれます。

それにscratchとの検索であればjavascriptという文字列は完全に無関係でノイズのようなものなので、その評価値は全体の評価値には関与しない方がいいということもあったりします。

もし①「scratch, scratch」と②「scratch, javascript」という文章があったとしてscratchで検索をかけると、ともに距離の最小値は0で①、②の評価が同じになってしまいます。ここは②よりも①のほうが選ばれるべきだと思うのでで、少々直感から離れています。ここで最小値ではなく調和平均を使うと改善されるかと思います。

2.
最小値をとるという動作は一文だけに適応されていますが、上と同じ理由は内容全体にも言える話なのでそこも和ではなく調和平均を使ったほうがいいかと思います。

3.

ARATAKU wrote:
そもそも、大量の候補の中から、曖昧検索をかける必要が無いような気がしてきました。
なぜなら、「アメリカ合衆国」を検索しようとして、「アメリカン合唱国」のように計算する人などいないからです。
見出しみたいな部分にだけ曖昧検索をかけて、google検索のように、「もしかして〇〇」のように出来るようにすれば良いと思います。
（見出し以外のところまで曖昧検索をかけていては、時間がかかって仕方が無いです。）

違う理由ですが、私も同じようなことを考えていました。
重いレーベンシュタイン距離ですが、これは従来のスライドするでもハミング距離で似たようなことができるからです。
具体的にはスライドはレーベンシュタイン距離の挿入、削除を模倣できます。
多分この処理は文字列検索のアルゴリズムを使うことで高速化できます。

gagagagagagagaqqww

わたしださんが言っていた「環境によっては改行しないとリストが省略される」問題直しました

地味にすれ違いっていう

kakurenbo

調和平均、とても賛成ですが、また繰り返しが多くなる気が…他を短縮するか…

Last edited by kakurenbo (April 12, 2019 12:41:21)

watashida

kakurenbo wrote:
調和平均、とても賛成ですが、また繰り返しが多くなる気が…他を短縮するか…

繰り返しの量は変わりません

kakurenbo

ZeroX_Gameさんが、「編集距離が一定以上超えたら無限を出力にして処理を切り上げる」
みたいなことを言ってましたよね。
その応用で、そもそも「候補」リストから削除すれば良いのではないでしょうか？

Last edited by kakurenbo (April 13, 2019 07:29:04)

gagagagagagagaqqww

わたしの理解(低め)が正しければ、「候補」リストをもとにレーなんとか距離を測っているので、候補を選別するためにまず候補を使って測らなければいけないという矛盾が生じます。
すれちがい

Last edited by gagagagagagagaqqww (April 12, 2019 12:58:52)

watashida

#127の1は最小値のほうがいいみたいです。

ARATAKU

kakurenbo wrote:
ARATAKUさんが、「編集距離が一定以上超えたら無限を出力にして処理を切り上げる」
みたいなことを言ってましたよね。
その応用で、そもそも「候補」リストから削除すれば良いのではないでしょうか？

そんなこと言ってません。(誰が言ってたかな・・・。）

Last edited by ARATAKU (April 13, 2019 07:20:46)

gagagagagagagaqqww

いよいよ検索プログラムの理屈が私の知識的に理解できなくなってきたのでとりあえず使いやすさ進化させますね。

ARATAKU

https://scratch.mit.edu/projects/284065527/
レーベンシュタイン法を使わずに検索する物を作りました。
早くなりました。

kakurenbo

ARATAKU wrote:
そんなこと言ってません。(誰が言ってたかな・・・。）

ZeroX_Gameさんでした。(ホント申し訳ありません///)

gagagagagagagaqqww

ちょっとHTML的なアレの開発に着手してみます
ショーテルで発表するもののネタに困ってたとこだし

gagagagagagagaqqww

無事挫折。
エディターがめんどくさすぎる…

rs1019

gagagagagagagaqqww wrote:
ちょっとHTML的なアレの開発に着手してみます
ショーテルで発表するもののネタに困ってたとこだし

了解っす

Discuss Scratch