1

この質問は、インタビューで私の友人の1人に尋ねられました。

2つのキーワードが与えられた場合、大きなテキストで与えられたキーワードを含む最短のフレーズの長さを見つける必要があります。キーワードは、そのテキスト内で任意の順序で表示できます。制約：効率的なデータ構造を維持して、異なるキーワードを使用するクエリでテキストを解析する必要がないようにします。

例えば。キーワード：「1」、「4」テキスト：「1、2、3、4、5、4、6、1」

ここで、そのような最短のフレーズは、「1、2、3、4」ではなく「4、6、1」です。

私たちが念頭に置いている解決策は次のとおりです。テキストのすべての単語を使用してBSTを構築します。各ノードは単語の場所を維持します。（これはソートされたリストになります）クエリが来たら[O（logn）]両方の単語を検索し、[O（n）]でそれらの場所の最小差を見つけて効果的に[O（nlogn）]にします。

もっとうまくやれるでしょうか？

4

4 に答える 4

2

逆索引にはハッシュ テーブルを使用できます。つまり、単語 (キーワード) からテキスト内の位置のソート済みリストへのハッシュ テーブルです。クエリの 2 つのキーワードを取得すると、それらの発生レコードを検索するのは O(1) 操作です。

発生位置間の最小差を見つけることは、O(k) 操作です。ここで、k は、より長い発生リストの長さです。変則的なケースでは、k が n に近い可能性がありますが、現実的にはそうではありません (「the」と「a」を 2 つのキーワードとして使用する場合を除きますが、ストップ ワードとして知られるこれらのタイプの単語は、通常、完全な単語から除外されます)。とにかくテキスト検索）。

通常の設定では、k は n に比べて非常に小さいため、これは非常に高速である必要があります。つまり、O(1) + O(より一般的なキーワードの出現回数) です。

于 2012-05-08T05:51:30.650 に答える
1

これは動的計画法を使用して解決できるようです。一般性を失うことなく、質問を次のように言い換えることができます。

検索空間S = {s1, s2, ..., sn}、針のペアが与えられると、次のような(si, sj)位置のペアを見つける必要があります。(k, l)

  1. (sk, sl) == (si, sj)
  2. distance(k, l)最小です。

この問題の再帰的な解は、次のように定式化できます。

Cost(m) =

  1. LARGEST_NUMBER, if m = 0
  2. Min (Cost(m-1), distance(S[m], Latest_si)), if m > 0 and S[m] == sj
  3. Min (Cost(m-1), distance(S[m], Latest_sj)), if m > 0 and S[m] == si
  4. Cost(m-1), if m > 0 and S[m] != (si, sj)

どこ、

  1. Cost(m)最適化関数です。(si, sj)検索空間内の最小距離を表しますS[1:m]。
  2. Latest_siは の最新の位置ですsi。
  3. Latest_sjは の最新の位置ですsj。

これは、 to storeO(n)のスペースの複雑さを持つボトムアップ ループに変換できます。O(n)Cost

Python での上記のアルゴリズムの実装は次のとおりです。

def min_phrase (S, si, sj):
  Cost = []
  for i in S:
    Cost.append([len(S), [-1, -1]])

  latest_si = -1
  latest_sj = -1

  for idx, v in enumerate(S):
    if v == si:
      if latest_sj >=0:
        cost = idx - latest_sj
        if cost < Cost[idx - 1][0]:
          Cost[idx] = [cost, [latest_sj, idx]]
        else:
          Cost[idx] = Cost[idx - 1]
      else:
        Cost[idx] = Cost[idx - 1]

      latest_si = idx

    elif v == sj:
      if latest_si >=0:
        cost = idx - latest_si
        if cost < Cost[idx - 1][0]:
          Cost[idx] = [cost, [latest_si, idx]]
        else:
          Cost[idx] = Cost[idx - 1]
      else:
        Cost[idx] = Cost[idx - 1]

      latest_sj = idx

    else:
      Cost[idx] = Cost[idx - 1]

  return Cost[len(S) - 1]


if __name__ == '__main__':
  S = ("one", "two", "three", "four", "five", "four", "six", "one")
  si = "one"
  sj = "four"

  result = min_phrase(S, si, sj)
  if result[1][0] == -1 or result[1][1] == -1:
    print "No solution found"
  else:
    print "Cost: {0}".format(result[0])
    print "Phrase: {0}".format(" ".join(S[result[1][0] : result[1][1] + 1]))
于 2012-05-08T06:09:48.973 に答える
0

ポイントを逃しているかもしれませんが、これは、String[] text派手なデータ構造の代わりに O(n) の単純な配列を使用して実行できるようです。

  • 1* テキストを配列にロードします。
  • 2* キーワードの場所を見つけて、xその位置を追跡します。
  • 3* キーワードの場所を見つけて、yその位置を追跡します。
  • 4* x と y の間の距離をマークします。
  • 5*初回セットminx = xとminy = y
  • 6* x と y を交互に見つけ続け、新しい短い距離が見つかるたびに minx と miny の値を変更します。
  • 7* 最後に、minx と miny で囲まれた部分文字列を返します
于 2012-05-08T12:03:32.147 に答える
0

まず、テキストをフレーズに分割します。これらのフレーズのそれぞれに番号を割り当てます。現在、テキスト内の各単語は、これらのフレーズのいくつかに含まれています。句の長さを配列に入れます。順序付けられた配列として存在するフレーズの番号を使用して、単語をハッシュ テーブルに入れます。

2 つの単語を含む最短のフレーズが必要な場合は、最初に単語の 2 つの prace-array を取得し、次に積集合を実行し、結果のフレーズ番号のフレーズの長さを調べます。最短を選びます。

于 2012-05-08T08:21:27.863 に答える