問題タブ [longest-prefix]

IP アドレス 192.168.0.1 と、サブネット IP アドレスを格納する列 next_hop_subnet を含むテーブルが与えられた場合、次の PostGRESQL ロジック、精度またはパフォーマンスに関して問題があると思いますか?

同じくらい良いマッチが複数あり得るので、これは二段階でやるしかないと思います。助言がありますか？

2 つの配列の最も長い共通プレフィックス (元のインデックス 0 から始まるサブ配列) とサフィックス (元のインデックス -1 で終わるサブ配列) を取得する最良の方法は何ですか? たとえば、次の 2 つの配列があるとします。

これらの配列の最も長い一般的なプレフィックスは次のとおりです。

これらの配列の最も長い一般的なサフィックスは次のとおりです。

インデックス 0/-1 の要素が元の配列で異なる場合、共通のプレフィックス/サフィックスは空の配列にする必要があります。

個々の単語 (句ではない) の配列の大規模なセットを想定します。たとえば、

個々の単語の別の配列が与えられた場合、「ブルート フォース」ソリューション (つまり、連続的な文字列マッチング) 以外に、左から右へ最も長い一般的な一致を見つける最も効率的 (最速) な方法は何でしょうか?

たとえば、配列が与えられた場合{"One", "two", "three", "four", "five"}、上記のリストで最も長い一般的な一致は{"One", "two", "three", "four"}.

私は約5000語のリストを持っています。特定の単語のそれらの単語の中で最長のプレフィックスマッチを見つけたいです。たとえば、私のリストには次のものがあります。

ここで 12134 を検索すると、結果は 121 (最長一致) になります。私はそれがさまざまな方法でできることを知っています。しかし、最も効率的な方法は何ですか？

現在、Symfony2 でFOSElasticaBundleを使用していますが、最長のプレフィックスに一致する検索を作成するのに苦労しています。

これを使用してオートコンプリートのような検索を実行するためにインターネット上にある 100 の例を認識しています。しかし、私の問題は少し異なります。

オートコンプリート タイプの検索では、データベースは最長の英数字文字列 (文字数) を保持し、ユーザーは最短部分のみを提供します。たとえば、ユーザーが「jho」と入力すると、Elasticsearch は「Jhon、Jhonny、Jhonas」を簡単に提供できるとします。

私の問題は逆です。最も長い英数字の文字列を提供したいのですが、Elasticsearch にデータベース内の最大の一致を提供してもらいたいのです。

例: "123456789" を指定すると、データベースは [12,123,14,156,16,7,1234,1,67,8,9,123456,0] を持つことができます。ユーザーが提供した番号は「123456」です。

私は Elasticsearch を使い始めたばかりなので、作業設定などにあまり詳しくありません。

不明な情報や不足している情報がある場合はお知らせください。詳細をお知らせします。

更新 1 (ヴァルの 2 回目の更新を使用)

インデックス: 1800 以上のインデックスをダウンロード

ボーナス質問

その検索に数値の配列を提供し、毎回クエリを実行することなく効率的な方法でそれぞれに一致するプレフィックスを取得したいと思います

サブネットのテーブルに存在する (指定された 4 ドット形式の IP アドレスの) 最長一致を見つけるための MySQL クエリを作成したいと考えています。

LEFT JOIN最終的に、別のテーブルの最長一致と結合された 1 つのテーブルにすべての四角形の IP アドレスを表示するを作成したいと思います。一時テーブルを作成したり、ネストされたクエリとして構造化したりしたくありません。

私はややMySQLの初心者ですが、私が考えているのは次のようなものです:

minimum_ip_valueおよびは、特定のサブネットで可能なmaximum_ip_value最小および最大の 10 進形式の IP アドレスです。たとえば、サブネット 172.16.0.0/16 の場合:

との間のすべて<list of subnet intervals>の区間を含むsubnets_table<given ip address>minimum_ip_valuemaximum_ip_value

また、複数の間隔に が含まれている<given ip address>場合は、最小の間隔 (つまり、最小のサブネット、または最も具体的で「最長」の一致) が結合されます。

最終的に、私が本当に欲しいのは、subnet_idその間隔に対応する値だけです。

だから私の質問は：

1) 任意の数のパラメータで LEAST() 関数を使用できますか? のすべての行、より具体的にはとsubnets_tableの間のすべての行の間隔を比較し、最小の間隔を選択したいと思います。minimum_ip_valuemaximum_ip_value

LEFT JOIN2)クエリ内でこのすべての計算を実行できますか? 高速でカプセル化され、同じデータの繰り返しのクエリを回避する提案があれば問題ありません。

これを 1 回のクエリで (つまり、各 IP アドレスのサブネット テーブルをクエリせずに) 実行できるかどうか疑問に思っていますが、それを除外するのに十分な知識はありません。これがうまくいかない場合は、別の角度から試すことができるので、お知らせください。

ありがとう。