问题标签 [hamming-distance]

我有 2 个序列文件。说 ham1.txt ：

等等

火腿2.txt：

我想将 ham1.txt 中的序列与 ham2.txt 中的序列匹配，具体取决于哪对具有最小汉明距离。我的python代码打印了它们之间的汉明距离。我只想要最合适的一对。这是我的代码

你能建议编辑吗？谢谢

我正在编写一个应用程序，该应用程序需要允许用户选择其位置半径范围内的元素。没有办法知道最终会有多少个位置，但它可能是数万个。进行搜索的用户是位置节点之一（而不仅仅是他们的手机或其他提交的任意位置）

我看到这样的答案：mysql lat lon calculation to show locations within radius但我担心这是一项非常严肃的工作，因为需要为每个“其他”位置计算所涉及的数学。

我正在考虑的另一种方法是有一个关系表来标识每个位置之间的距离（每次添加位置时我都会填充），授予它将有大量行来定义每个可能的关系，然后选择反对 *该表将非常快，尤其是在对距离进行索引的情况下。

希望从在 mySQL 中完成此操作的人那里获得一些建议，并且可以警告/建议我支持或反对最佳方法。

I'm interested in creating a program that will search for a certain string (known henceforth as string A) in a large library of other strings. Basically, if string A existed in the library it would be discarded and another string's existence would be checked for within the library. The program would then give me a final list of strings that did not exist as substrings within the large library. I was able to make a program that finds EXACT matches, but I need to add an additional module that allows the sub-string search to allow for partial matches. Namely, one or two of the sub-string characters would be alright. The list of string A's (which are all permutations of a,t,g,c in a 7-letter string 4^7 different ones) has difficulties with highly diverse libraries.

My initial thought was to use regex and perhaps a hamming distance algorithm to find all those partial matches. Basically this first attempt allows me to put a "?" or wildcard into all positions of the string A in question (1-7), but I can only get it into the first position. The wildcard would then allow me to search for partial matches of the particular string A in question. If this the wrong way to approach this problem, I'd gladly change it up. I used fnmatch as per suggestion on another question This is what I have so far:

This is my desired output:

primer = "tgatgag"

我有一个如下所示的 documentTermMatrix：

包装内tm中，可以计算 2 个文档之间的汉明距离。但是现在我想对所有汉明距离小于 3 的文档进行聚类。所以在这里我希望集群 1 是文档 1 和 2，而集群 2 是文档 3 和 4。有可能这样做吗？

我想打破 XOR 重复密钥，我现在对密钥和消息一无所知，只有我知道它正在使用重复密钥。使用重复密钥 XOR 加密后，编码的消息是 base64 的，所以我首先将 base 64 转换为 base16，这样更容易。我有说明，但我不太明白这一点。

1. 令 KEYSIZE 为密钥的猜测长度；尝试从 2 到（比如说）40 的值。编写一个函数来计算两个字符串之间的编辑距离/汉明距离。

2. 对于每个 KEYSIZE，取第一个 KEYSIZE 字节值和第二个 KEYSIZE 字节值，并找到它们之间的编辑距离。通过除以 KEYSIZE 来规范化这个结果。

3. 归一化编辑距离最小的 KEYSIZE 可能是关键。您可以继续使用最小的 2-3 KEYSIZE 值。或者取 4 个 KEYSIZE 块而不是 2 个并平均距离。

既然您可能知道 KEYSIZE：将密文分成 KEYSIZE 长度的块等，我得到了这个，其余的都很好，现在，我现在应该确切地知道这是否很好并尝试解码..

我在 Python 中为此编写了一个代码，它正在工作，但我不完全确定我是否正确地做到了这一点

给定一个二元方阵。我想得到所有可能的二进制矩阵，它们d相距汉明距离。

认为

那么相隔一 (d) 汉明距离的矩阵是

Matlab基础编码有什么帮助吗？

我正在尝试编写一个函数来匹配 ORB 功能。我没有使用默认匹配器（bfmatcher、flann 匹配器），因为我只想将图像中的特定特征与其他图像中的特征匹配。

我看到 ORS 描述符它是一个二进制数组。

我的查询是如何匹配 2 个特征，即如何找到 2 个描述符之间的汉明距离？

ORB 描述符：

谢谢。

目前我在一个有大量哈希值（字符串）的应用程序上工作。
当给定查询哈希值（字符串）时，搜索过程会遍历这些字符串并返回查询字符串和结果字符串之间的汉明距离小于给定阈值的字符串。

• 哈希值不是二进制字符串。例如“ 1000302014771944008”
• 所有哈希值（字符串）都具有相同的固定长度。
• 阈值不小（通常t>25）并且可以变化。

我想使用一种有效的算法而不是使用蛮力方法来实现这个搜索过程。
我已经阅读了一些研究论文（例如this和this），但它们适用于二进制字符串或低阈值。我还尝试了 Locality-sensitive hashing，但我发现的实现主要集中在二进制字符串上。

是否有任何算法或数据结构来解决这个问题？
也欢迎任何建议。先感谢您。

.

附加信息

非二进制字符串之间的汉明距离

考虑蛮力方法

1. 计算第一个哈希字符串和查询哈希字符串之间的汉明距离。
2. 如果汉明距离小于阈值，则将哈希字符串添加到结果列表中。
3. 对所有哈希字符串重复步骤 1 和 2。

我正在尝试计算两个十六进制字符串之间的汉明距离。首先，字符串从基数 16 转换为基数 10，然后对它们进行异或运算并计算位：

SELECT (CONV('b4124b0d195b2507', 16, 10)) ^ (CONV('eae26aebf1f139f9', 16, 10));

这导致 0。

独立运行

SELECT (CONV('b4124b0d195b2507', 16, 10));

和

SELECT (CONV('eae26aebf1f139f9', 16, 10));

给我我期望的答案（12975515996039881991 和 16925207911220722169）。

我的逻辑缺陷在哪里？

我需要计算四个分类群 L1、L2、L3 和 L4 的汉明距离。

我怎样才能这样做来计算所有四个的汉明距离？