5

私はたまたまPythonで二分探索を構築していますが、問題は二分探索構造全般に関係しています。

二分探索を使用して検索している約1000の適格な候補があると仮定しましょう。ソートされたデータセットを二等分し、このプロセスを繰り返して適格なセットを絞り込んで繰り返します。候補は単なる名前の文字列です (「ピーター ジャクソン」などの最初から最後までの形式)。

hi = len(names)
lo = 0
while lo < hi:
  mid = (lo+hi)//2
  midval = names[mid].lower()
  if midval < query.lower():
    lo = mid+1
  elif midval > query.lower():
    hi=mid
  else:
    return midval
return None

ここから適応したこのコード: https://stackoverflow.com/a/212413/215608

これが問題です。上記の手順では、完全に一致するものが 1 つあるか、結果がまったくないことを前提としています。クエリが単に "Peter" に対するものであったが、姓の異なる複数の Peter がいる場合はどうなるでしょうか? すべてのピーターを返すには、二分された「ビン」が、適格な結果を除外するほど小さくならないようにする必要があります。すべてのピーターを返すには、二分プロセスを停止して、正規表現/通常の古い文字列の一致のようなものに譲る必要があります。

私は、このタイプの検索が何と呼ばれるかほど、これを達成する方法を尋ねているわけではありません...「ビンサイズ」の区切り基準を持つバイナリ検索は何と呼ばれていますか? 条件付きでデータセットを二等分し、基準が満たされると、クエリに効果的に末尾のワイルドカードが存在することを保証するために、他の形式の文字列一致にフォールバックするもの (したがって、"Peter" の検索は "ピーター・ジャクソンズ」と「ピーター・エドワーズ」)

うまくいけば、私が何を意味するのかが明確になりました。典型的な DB シナリオでは、名前が分離されている可能性があることを認識しています。これは、概念実証として意図されているだけです。

4

2 に答える 2

2

このような 2 段階検索は見たことがないので、名前がよく知られているかどうかはわかりません。ただし、それを実行する方法を提案することはできます。

最初のステージを実行し、一致するものが見つからなかったとしましょう。

二分探索のペアと特別なコンパレータを使用して、第 2 段階を実行できます。bisect_left二分探索は、および とbisect_right同じ原則を使用します。特別なコンパレータが必要になるため、これらの関数を直接使用することはできませんが、実装の基礎として使用できます。

ではコンパレーターへ。リスト要素xを検索キーと比較する場合、コンパレータは残りの要素kのみを使用して無視します。したがって、「Peter」を検索すると、リスト内のすべての Peter がキーと等しくなります。したがって、toは、リスト内のすべてのピーターを含む範囲を提供します。x[:len(k)]xbisect_left()bisect_right()

O(log n)これらはすべて、比較を使用して実行できます。

于 2012-12-17T20:15:08.243 に答える
0

バイナリ検索では、完全一致または一致する領域にヒットします。
したがって、あなたの場合、hi loを含む領域の上限と下限の境界を取得する必要があります(呼び出したとおり) Peter。すべての中間文字列を返します。

しかし、単語の次の単語を表示するようなことを目指す場合は、BST の代わりに Tries を調べる必要があります

于 2012-12-17T20:14:56.647 に答える