この探索アルゴリズムの名前は？2分探索法ではないっぽい

2分探索法は、検索対象が大小関係で並んでいる事が条件で、効率良く検索できる方法と思います。

＞「文章を半分ずつ入れて…
ならば、単純に「分割チェック」か「分割確認」か「分割探索」か「分割検索」くらいが適当なお名前ではないかと思います。😃

おもしろいお話ですねー♪
考えながら書いてみます。

まず、探索アルゴリズムは、特定のデータ（NGワード）を、大量のデータ中（送信コメント）から探し当てる方法です。
「送信」ボタンを押すと、マイネ王のプログラムがNGワードを探し当てるわけです。（たぶん全探索をしていると思います）

我々ユーザーは、NGワードを含む事はわかるのですが、
・どこにあるかわからない
・NGワードが何かもわからない
という状態です。

ですので、「不明なワード」をデータの中から探索する、という事は不可能なのです！
ですから、ユーザーは「どこ」にあるかの「場所」を探すしかありません。で探すのは誰なのかと言うと、探すのはマイネ王のプログラムです。

ですから、いわゆる「探索アルゴリズム」ではないですよね。
と書きましたが、、、
いやいや探索アルゴリズムなのかも…？もうちょっと勉強して来ます！

こことか見ましたが、難しくてにわかには理解できません💧
https://qiita.com/e869120/items/25cb52ba47be0fd418d6#5-はやい探索法半分全列挙

正しくないかもしれませんが、分割統治法とかになるような気がします。divide and conquerというテクニックかなぁ

除外検索じゃ無いかなぁと
要するに単語を可能な限り分割して、引き算して試すんですよね？

ああ、すいません、アルゴリズムですよね
線形探索かな？

確かに質問対象のアルゴリズムは今回の分割統治法と除外検索の両方の概念を持っていますね。それに「2分割」という概念を加えた「２分割探索法（適当な造語）」の様なドンピシャなアルゴリズム名が有るような気がしてなりません。
立ち位置が微妙過ぎて無いのかな？

私なら「篩いに掛ける」、もしくは「篩」そのものですかね

海外の人の感覚でどういう言葉を使うかは思いつきませんでした

ああ、あと「粗密探索」が近いかも知れませんね
名称はあまりつかった経験がなくピンとこないですが、粗く処理して、その後、密の処理をする手法はよく使いますね

考えてみましたが、やっぱり「二分探索」ですよね。
これが仮に普通の探索で、探索したいデータ（NGワード）が決まっている場合であれば、

①対象はソート済みである必要あり
②探索したいデータ（NGワード）が中央の要素より大きいか小さいかを調べる。
③これにより、データが全体の前半分にあるか後ろ半分にあるかを判定する

という事なのですが、
そもそも探したいデータ（NGワード）がわかりませんので、中央値との大小比較こそできませんが、
上記②に該当する作業が「文章を半分ずつ入れて引っ掛かるか調べる」だと思います。

マイネ王のプログラム内では、半分の文章を全検索しているのでしょうけど、それは知ったこっちゃありません。

ユーザーが、半分の文章の中にワードがあるか無いかを調べる方法が「半分だけ送信してみる」という行為に当たります。
なので、1/2ずつ文章を割って確かめる方法は、「二分探索」アルゴリズムではないですかねー。

仮に線形探索の場合、まずNGワードが何桁かわからないので、１桁ずつチェックして行く必要があります。

①１桁と仮定して探索
最初の１文字だけ送信
次の１文字だけ送信、
と繰り返して行く。エラーになればNGワード。

②２桁と仮定して探索
最初の１～２文字目だけ送信
次に２～３文字目だけ送信
３～４文字目だけ送信
と繰り返して行く。エラーでNGワード。

③３桁と仮定して探索
最初の１～３文字目だけ送信
次に２～４文字目だけ送信
３～５文字だけ送信
と繰り返して行く。エラーでNGワード。

という感じですね。

---
分割統治法はソートのアルゴリズムですよね。
結合する必要は無い気がします。

NGワード探索は、我々ユーザーが何回「送信」ボタンを押すか、それが少ない方が速い検索、となります。

送信ボタンを押した後にマイネ王のプログラムが何回文字列検索するか、という回数は関係ありません。
そもそもプログラムの中がどんなアルゴリズムで動いているか知る由もありませんしね。

ユーザーがどうやって「送信」を押すか、のアルゴリズムが問題なのです。
なので線形に総なめしていない事は明らか。
最小単位まで分割して比較、をしていない事も明らか。

>> さと さん

うーん🤔ムヅカシイなぁ😵
だけど、折角だからもうちょっと考えてみますね

他のトピックで読んだのですが、「そうさつ　する」と書くとエラーになる場合で考えてみたんですが…
「相」という文字が単独でNG扱いになっている可能性は低く
「そうさつ」（敢えてひらがな表記です）と言う単語
若しくは「さつ」の漢字表記の何方か片方がNGなのか両方がNGなのかこちからは判りません
或いは、連語として「◯◯さつする」そのものがNG扱いである可能性もありますね

そうなると、さとさんのおっしゃる事が正しい様に思えますね

分割統治法は日本語訳がうまく言葉を使っていないと思います。最初にこの話題を見たときに考えたことですが、前半後半に分けても両方ともにNGワードが含まれる恐れがあると感じているあたりから、2分探索とは違うと感じているのかなと考えて分割統治法を提示してみました。

>> ぼちぼち さん

＞前半後半に分けても両方ともにNGワードが含まれる恐れがあると感じているあたりから、2分探索とは違うと感じているのかな

なるほど。確かに。

私は「ソート前提」という事で違うと感じているのかと思っていました。

まず問題を２つに分けます。
単語の認識と探索ですね。
単語の認識は、言い出すと切りが無いので、ここではAtomicとして考えます。「単語は簡単に認識できる」と思ってください（人間が認識するかコンピューターが認識するかも置いときます）。
「文章を半分ずつ入れて、引っ掛かったらまたその半分、と言う感じでNGワードを探す」
を単語に分割すると
文章　を　半分　ずつ　入れ　て　引っ掛かっ　た　ら　また　その　半分　と　言う　感じ　で　NGワード　を　探す
19個のAtomに分解できます。1Atomを○で表すと
○○○○○○○○○○○○○○○○○○○
2104まいまいさんの質問は、この中に１個黒丸が入っていて、それを探索するアルゴリズムと解釈できます。
19個を前半の10個と後半の9個に分けて、とあるアルゴリズム（ブラックボックス）に入れると黒丸が入っているかどうかを判定してくれます。
例えば、
前半：○○○○○○○○○○
後半：○○○○○○○○○
で、前半に黒丸と判定されたと仮定します。次のステップは、
前半：○○○○○
前半：○○○○○
をブラックボックスのアルゴリズムに入れて黒丸の判定をさせます。

これって、Binary Searchと原理的には同じですね。通常のBinary Searchは、黒丸（当たりとも言う）が入っているのが前半か後半かの判定を数値の大小で行っています。当たりの判定を数値の大小で行うか、ブラックボックスにさせているかの違いだけで、探索効率の理論値も一致します。
なので、Binary Searchと呼んで差し支え無いと思います。

言い忘れました。
NGワード、黒丸、当たり、は１個だと仮定してます。０個や複数個の可能性がある場合には、話がかなり厄介になります。

>> Ticket to the moon さん

私も全く同じ考えです。
バイナリーサーチと二分探索って、日本語か英語かの違いだけで同じですよね？

>> Ticket to the moon さん

スッキリまとめて頂きありがとうございました。
二分探索法で大小関係以外を扱った説明は今回見つからなかったので何とも言えませんが、おかげさまで少なくとも今回扱ったアルゴリズムは二分探索法と同じ、もしくはそれを包含すると思いました。

あと思ったのが、今回扱ったNG ワードを含んだ投稿文は名義尺度のように見えて、表題のアルゴリズム&mineoのNGワードフィルターにおいては順序尺度のような性質を持っているのですね。つまり2分割と投稿を繰り返しても投稿文の中の文字の前後関係は変わらないため、あたかもソートされた数列と同じように、二分探索法のようなものが適用できるのだと思いました。

>> さと さん

＞バイナリーサーチと二分探索って、日本語か英語かの違いだけで同じですよね？
テクニカルタームは１対１対応でないとならないってお約束があるので、同じで間違いないです。
コンピューター用語の場合、あまりに本質から離れた単語が選ばれるので（翻訳する人のセンスが無い）ので、日本語で勉強すると混乱するばかりだと判断して、それ以後は英語でのみ勉強してます。そのため、日本語の用語を知らないんです。
今回の「二分探索」ぐらい的確な単語が選ばれていれば、日本語でも問題無いですね。でも、ダメな場合が多いです。

>> 2104まいまい さん

＞名義尺度のように見えて、表題のアルゴリズム&mineoのNGワードフィルターにおいては順序尺度のような性質を持っているのですね。
いえ、違います。
まず、探索対象が１個の場合に限って書きます。複数の場合は、書くのに相当に暇がかかりそうなので、放ったらかすと思います、ゴメンナサイ。
探索を２つの部分に分けます。
「当たりが入っているかどうかを判定するアルゴリズム」と「１個になるまで篩い落とすアルゴリズム」です。
最初に教科書に書いてあるBinary Searchに関して説明します。
例として、0-9の10個の数値から8を探索してみます。
Binary Searchでは、最初に順番に並べます（Sort）。
０　１　２　３　４　５　６　７　８　９
【個数】で真ん中の数字を選びます、この場合「４」でも「５」でも問題ないのですが、取り敢えず「４」を選んでみましょう。「４」の真後ろに切れ目がある感じですね。この切れ目の前に当たりがあるのか、後ろに当たりがあるのかを判定します。この判定は非常に簡単で、「４＜８」なので、後ろの半分に当たりがあると判定できます。従って、
５　６　７　８　９
から、「８」を探索することになります。再度、【個数】で真ん中の「７」を選びます。「７＜８」ですから、後ろの半分に目標はあるはずです。「７」を除いた後ろの半分は、
８　９
ですね。同様に【個数】で真ん中の数字を選ぶと「８」ですので、「８＝８」で探索終了となります。
これはソートしてあるから簡単なんですね。ソートしてなければ、
９　５　８　６　４　１　２　０　７　３
同じように【個数】で真ん中の「４」を選んでも、「４＜８だから、、、どっち？」とか「４＜８だからどうした」となります。
順序が重要なのは、「当たりが入っているかどうかを判定するアルゴリズム」の方なんですね。

字数制限にかかりましたので、分割です。
−−−−ここから


今回の2104まいまいさんの質問の場合を考えてみます。
○　□　△　▽　☆　♡　♤　♧　♦　◎
前半と後半に分けます。
○　□　△　▽　☆
♡　♤　♧　♦　◎
ブラックボックスの「当たりが入っているかどうかを判定するアルゴリズム」にこの２個を渡すと、前半は「当たり無し」、後半は「当たり有り」と返して来ますので、今度は
♡　♤　♧　
♦　◎
でブラックボックスに判定を依頼して、また後半に「当たり有り」が返ってきます。次に、
♦
◎
で判定を依頼すると、前半を渡したら「当たり有り」、後半を渡して「当たり無し」となります。最後に前半を半分にしようと思っても、１個なので半分にできません。ここで、探索終了となります。

整理すると、「教科書に書いてあるBinary Searchで順序が重要なのは、当たりが入っているかどうかの判定が楽になるから」で、今回の件では、「順序は利用できない」となります。