将相同字符多次进行哈希处理

Question

我正在做一个编程挑战，其中一个挑战让我感到很疯狂。在这个挑战中，我需要计算一个字符串的MD5值。该字符串以以下形式给出：n[c]，其中n为数字，c为字符。例如：b3[a2[c]] => baccaccacc。一切都进行得很顺利，直到我收到了以下字符串：1[2[3[4[5[6[7[8[9[10[11[12[13[a]]]]]]]]]]]]. 这个字符串转换成一个包含6227020800个“a”的字符串，大小超过6GB，因此几乎不可能在实际时间内计算它。所以，我的问题是：MD5有什么性质可以在这里使用吗？我知道必须有一种方法在短时间内完成计算，我怀疑这与所有字符串都是同一字符重复多次有关。

- Lars

---

这可能会很简单，反向查找并找到第一个出现的 [，将其后面的字符（a）替换为 [ 前面的数字（13，因此为 13*‘a’），然后将该字符串存储在变量中，查找下一个 [ 并取 mystoredstring*num 等等。 - Torxed

@Torxed，这个问题不是关于从紧凑表示生成实际字符串的（这将是字母a的6227020800次，正如OP已经说明的那样），而是关于高效地计算如此大字符串的MD5哈希。 - Carsten

我可以在我的机器上用大约14秒的CPU时间进行计算。你如何定义“实用时间”？ - Aya

@Aya 该死，我需要22秒 :-) 68df0fa...？ - Carsten

Answer 1

你可能已经创建了一个（递归）函数，以产生单个值作为结果。相反，你应该使用生成器将结果作为字节流生成。然后，你可以将这些字节逐个输入到MD5哈希例程中。这种方式不会影响内存使用量，只会影响计算时间，所以流的大小并不重要。

以下是使用单遍解析器的示例：

import re, sys, md5

def p(s, pos, callBack):
  while pos < len(s):
    m = re.match(r'(d+)[', s[pos:])
    if m:  # repetition?
      number = m.group(1)
      for i in range(int(number)):
        endPos = p(s, pos+len(number)+1, callBack)
      pos = endPos
    elif s[pos] == ']':
      return pos + 1
    else:
      callBack(s[pos])
      pos += 1
  return pos + 1

digest = md5.new()
def feed(s):
  digest.update(s)
  sys.stdout.write(s)
  sys.stdout.flush()

end = p(sys.argv[1], 0, feed)
print
print "MD5:", digest.hexdigest()
print "finished parsing input at pos", end

- Alfe

---

是的，这就是我一直在寻找的属性。感谢您无价的帮助。 - Lars

Answer 2

利用哈希的优良特性：

import hashlib
cruncher = hashlib.md5()
chunk = 'a' * 100
for i in xrange(100000):
    cruncher.update(chunk)
print cruncher.hexdigest()

调整轮数（x = 10000）和块的长度（y = 100），使得 x * y = 13!。重点是将您的字符串分成块（每个块长度为 x 个字符），连续进行 y 次算法处理。

- Stefano Sanfilippo

Answer 3

所有哈希函数都是设计用于处理字节流的，因此您不应该先生成整个字符串，然后再对其进行哈希 - 您应该编写生成器，生成字符串数据块，并将其提供给MD5上下文。 此外，MD5使用64字节（或字符）缓冲区，因此最好将64字节的数据块提供给上下文。

- Nickolay Olshevsky