如何在Python中对一行进行哈希处理？

Question

我正在尝试在Python中实现以下算法[1]：

问题：（行压缩）让A成为一个有界度数d的n x m数组（即，A的每个元素都是一个整数a，满足0<a<d），并且令k为A的不同行数。找到一个k x m数组A'，使得A的每一行都出现在A'中。

方法：（哈希）将A的行哈希到表中，跳过重复项并将其余项添加到A'中。

我不明白如何在Python中哈希一行？

好的，我想了解“将A的行哈希到表中”是什么意思。我的理解是这样的。假设我有一个像这样的矩阵：

A = [[1, 2, 3, 4], 
     [1, 2, 3, 4],
     [6, 7, 5, 4]]

因此，我对它的行进行哈希处理（以某种方式），然后得到：

B = [x1, x2, x3]

其中xi是行i的哈希值。因为行1和行2相等，所以我会得到x1=x2。既然我得到了x1=x2，我将保留一个，并最终得到：

A' = [[1, 2, 3, 4], 
      [6, 7, 5, 4]]

我是正确的吗？如果是，我该如何在Python中实现这样的算法？

谢谢。

---

[1] D. Comer，“使用Tries删除有界度数组的重复行”，普渡大学，1977年。

- Kira

---

你在找字典吗？ - Padraic Cunningham

我想，这是一个哈希表吗？ - Kira

是的，这就是你在Python中用于Trie的内容。 - Padraic Cunningham

Answer 1

首先，您需要删除重复行。为此，您可以使用set，但首先需要将所有行转换为不可变对象类型。

您可以将它们转换为tuple：

>>> A = [[1, 2, 3, 4], 
...      [1, 2, 3, 4],
...      [6, 7, 5, 4]]
>>> 
>>> map(tuple,A)
[(1, 2, 3, 4), (1, 2, 3, 4), (6, 7, 5, 4)]

然后您可以使用 set。由于 set 使用哈希函数，因此结果将自动进行哈希处理：

>>> set(map(tuple,A))
set([(1, 2, 3, 4), (6, 7, 5, 4)])

- Mazdak