問題タブ [hamming-distance]

データ構造プロジェクトの場合、一度に1文字だけ変更して、 2つの単語（"cat"となど）の間の最短経路を見つける必要があります。"dog"パスを見つけるために使用するスクラブルの単語リストが提供されます。例えば：

幅優先探索を使用して問題を解決しましたが、より良いものを探しています（辞書をトライで表現しました）。

より効率的な方法（速度とメモリの観点から）についていくつかアイデアを教えてください。ばかげているおよび/または挑戦的な何かが好ましい。

私は友人の一人（彼は後輩です）に尋ねました、そして彼はこの問題に対する効率的な解決策はないと言いました。彼は、私がアルゴリズムのコースを受講したときに、その理由を学ぶと言いました。それについて何かコメントはありますか？

私たちは言葉から言葉へと移動しなければなりません。行くことはできませんcat -> dat -> dag -> dog。トラバーサルも印刷する必要があります。

kd ツリーについて読みましたが、空間の次元が高い場合は非効率的です。値のデータベースがあり、クエリから特定のハミング距離内にある値を見つけたいと考えています。たとえば、データベースは 32 ビットの数値のリストであり、クエリ値との差が 3 ビット未満のすべての数値を見つけたいとします。

MultiVariate Partition trees についてどこかで聞いたことがありますが、適切なリファレンスが見つかりませんでした。min-Hash の方が適切な近似値を提供することは知っていますが、正確な答えが欲しいです。

上記の結果は8.

それを実装する方法は？

特定のCRCによって生成されたコードのハミング距離を見つける方法は？

たとえば、4ビットと11ビットのデータの次数の生成多項式があるとします。

これらの情報のみに基づいてHDを計算するにはどうすればよいですか？

N 個の固定長文字列を持つデータベースがあります。同じ長さのクエリ文字列があります。問題は、q までのハミング距離が最も小さい最初の k 個の文字列をデータベースから取得することです。

N は小さく (約 400)、文字列は長く、長さは固定されています。データベースは変更されないため、インデックスを事前に計算できます。クエリは大きく異なります。キャッシングや事前計算はオプションではありません。毎秒たくさんあります。k-1 の結果が 0 に一致する場合でも、常に k の結果が必要です (ハミング距離でソートし、最初の k を取得するため、局所性に依存するハッシュや同様のアプローチでは実行できません)。kd-tree および同様のスペース分割は、おそらく線形検索よりもパフォーマンスが低下します (文字列は非常に長くなる可能性があります)。BK-tree が現時点では最良の選択ですが、必要以上に遅く複雑です。

実際のハミング距離を計算するために k <= t << N エントリを残して、ほとんどのエントリを非常に少ないステップで破棄するインデックスを構築するアルゴリズムがあるように感じます。

レーベンスタイン距離に基づくファジー文字列マッチングを提案する人々 - ありがとう、しかし問題ははるかに単純です。一般化された距離メトリック ベースのアプローチ (BK ツリーなど) は優れていますが、上記の事実を利用するものがあるかもしれません (小さな DB/長い固定サイズの文字列、単純なハミング距離)

リンク、キーワード、論文、アイデア？=)

誰かこの関数を書いてください

なぜ p++ の前に * を付けるのですか?

答え: 「同じだから」ということで、コードを修正してしばらく怒っていました。

これをstackoverflowと共有したいと思います。例：

char s[6]="こんにちは";

それは何をしますか？

これは ++ プリインクリメント (ポインター上) を評価し、次に逆参照演算子 * を評価するため、char 値 'e' ("hello" の 2 番目の文字) が返されます (この場合は使用されず、生成される可能性がありますコンパイル時の警告)、ポインターは 'e' (位置 1) から指します。

それは何をしますか？

これは、逆参照演算子 * を最初に評価するため、少し奇妙です。したがって、char 値 'h' (この場合はどちらも使用されません) を許可し、次に ++ ポストインクリメント (ポインターへ) を許可します。 （再び）ポインターは「e」（位置1）から指します

それは何をしますか？

最後に、char の左辺値はありませんが、使用されていない場合は警告を生成せず、ポインターも「e」(位置 1) からポイントします。

これら 3 つの形式は、ポインター アドレスの観点からは同じことを行います。

IMHO それは一部のコンピューター言語 (ほとんどすべての人) の最悪のことです..

「コードとバグの間にはハミング距離がありません」

プログラミングに冗長性はありません. 法律の本を手に取り, その中にランダムな文字を書き込めば, 読めるようになりますが, プログラミング時にランダムに入力するとバグが発生します. 100% の精度.

4 ビット エラーを検出し、2 ビット エラーを回復できるようにしたいとします。では、ハミング距離はどうあるべきか?

d = Max{2r+1, r+1} にするか、d = s + r にするか (s は 4、r は 2) でしょうか。

返信ありがとうございます！

乾杯

分類したいk個の異なる入力に対してnビットのコードを生成したいと思います。このコードの主な要件は、エラー訂正基準です。つまり、異なる入力の任意の2つのエンコーディング間の最小ペアワイズ距離が最大化されることです。正確である必要はありません。概算で十分です。使いやすさと計算の実装の速度も優先事項です。

一般に、nは数百、kは数十になります。

また、k個の異なるnビットバイナリエンコーディング間の最小ハミング距離にかなり厳しい境界がありますか？

入力：グラフG出力：いくつかの独立したセット。すべての独立したセットに対するノードのメンバーシップは一意です。したがって、ノードは、それ自体のセット内のどのノードにも接続できません。パスの例を次に示します。

ここで明確化が求められたので、別の言い換え：

与えられたグラフをセットに分割して、

1. セット内のメンバーシップによって、ノードを他のすべてのノードと区別できます。たとえば、ノードiがセットAにのみ存在する場合、他のノードはセットAにのみ存在するべきではありません。

   ノードjがセットAとBに存在する場合、他のノードはセットAとBにのみ存在してはなりません。ノードのメンバーシップがビットパターンでコード化されている場合、これらのビットパターンには少なくとも1つのハミング距離があります。

2. 2つのノードがグラフ内で隣接している場合、それらは同じセットに存在してはならないため、独立したセットになります

例：Bには隣接ノードがありませんD => A、A => D

解決：

1. AB/
2. / BD

Aにはビットパターン10があり、そのセットに隣接ノードはありません。Bにはビットパターン11があり、隣接ノードはありません。Dには01があるため、すべてのノードのハミング距離は少なくとも1であり、隣接ノードはありません=>正しい

間違っています。DとAが接続されているためです。

1. ADB
2. / DB

Aのセットにはビットパターン10とDがあり、それらは隣接しています。Bにはビットパターン11があり、隣接ノードはありません。DにはBと同様に11があるため、このソリューションには2つのエラーがあるため、受け入れられません。

もちろん、少なくともlog(n)セットが必要なので、グラフ内のノードの数が増えるにつれて、これをより多くのセットに拡張する必要があります。

これにsat-solverを使用するために、私はすでにMAX-SATへの変換を作成しました。しかし、条項の数は非常に多いです。より直接的なアプローチがいいでしょう。これまでのところ近似値がありますが、正確な解または少なくともより良い近似値が必要です。

粒子群を使用して、任意のソリューションからより良いソリューションに向けて最適化するアプローチを試しました。ただし、実行時間はかなりひどく、結果は決して素晴らしいものではありません。動的アルゴリズムか何かを探していますが、この問題を分割統治する方法を理解することはできません。

コンピュータ ネットワークの授業で勉強しているときに、その教授は、サンプル コード内の 2 つの有効なコード ワード間のハミング距離について話しました。ハミング距離について読んだことがありますが、2 つの弦の間の距離の違いを知るという観点からは理にかなっています。例えば：

送信者はコード ワード 1 を送信し、エラーが発生し、受信者は 10100 を受信します。したがって、4 番目のビットが破損していることがわかります。これにより、次の理由により、ハミング距離は 1 になります。

2本の弦をXORすると1が1になるので、ハミング距離は1です。ここまでは理解できました。しかし、教授は次のように尋ねます。

• 標準の CRC-16 ビット プロトコルのハミング距離は?
• 標準の CRC-32 ビット プロトコルのハミング距離は?

私は少し混乱していて、誰かが助けてくれるかどうか疑問に思っていました. ありがとう。