如何优雅地在Ruby中计算单词的字谜签名？

Question

在这个问题中，我正在寻找一种优雅的（ruby）方式来计算这个答案中建议的单词签名。

建议的想法是对单词中的字母进行排序，并且对重复的字母进行运行长度编码。例如，“mississippi”首先变成“iiiimppssss”，然后可以进一步缩短为“4impp4s”。

我相对较新于ruby，虽然我可以将某些东西捆绑在一起，但我相信这对于有更多ruby经验的人来说只是一个一行代码。我很想看到人们的方法并提高我的ruby知识。

编辑：澄清一下，计算签名的性能对于我的应用程序并不重要。我正在寻找计算签名以便将其与大型单词数据库中的每个单词一起存储，然后查询具有相同签名的单词（即给定单词的所有变位词，实际上是英语单词）。因此，重点在于空间。 "优雅"部分只是为了满足我的好奇心。

- frankodwyer

Answer 1

创建一个字母排序列表的最快方法如下：

"mississippi".unpack("c*").sort.pack("c*")

使用该方法比split('')和join()方法更快。为了进行比较，最好将数组重新组合成字符串，这样就不必比较数组了。

- martinus

---

你能用测量数据支持这个说法吗？例如，在一个包含10,000个单词的列表上，速度会快多少（例如/usr/dict/words）？ - Norman Ramsey

这很有趣，但非常晦涩。 - Zach Langley

好的，一个快速比较：使用Ruby 1.8.7时为5.5秒，使用unpack和pack会稍微快一些，为8.5秒。我认为在JRuby上差异更大，但我不太记得了。我已经对我的变位词查找器进行了调优：http://martin.ankerl.com/2008/08/09/two-word-anagram-finder-algorithm/ - martinus

这5.5秒钟的内容包含了320,000个单词，存储在一个字典中。 - martinus

Answer 2

我也不是很懂Ruby，但正如我在另一个评论中指出的那样，这似乎对所描述的算法有效。

s = "mississippi"
s.split('').sort.join.gsub(/(.)\1{2,}/) { |s| s.length.to_s + s[0,1] } 

当然，您需要确保单词是小写的，不包含数字等。

根据请求，我将尝试解释代码。如果我没有完全正确地使用Ruby或正则表达式术语，请原谅我，以下是说明。

我认为split / sort / join部分非常简单。对我来说有趣的部分从调用gsub开始。这将使用后面跟随的块的返回值替换与正则表达式匹配的子字符串。正则表达式找到任何字符并创建一个反向引用。那就是“(.)”部分。然后，我们使用评估为第一部分匹配到的任何字符的回溯引用“\1”继续匹配过程。我们希望该字符被找到至少两次，以获得总最小出现次数为三。这是使用量词“{2，}”完成的。

如果找到匹配项，则将匹配的子字符串作为参数传递到下一个代码块中，因为有“|s|”部分。最后，我们使用匹配子字符串长度的字符串等效形式，并附加组成该子字符串的任何字符，然后返回连接的值。返回的值替换原始匹配的子字符串。由于它是原始字符串上的全局替换，所以整个过程将继续进行，直到没有任何东西可以匹配。

如果这很困惑，请原谅我。通常情况下，对我来说更容易将解决方案可视化，而不是清晰地解释它。

- Robert Simmons

---

+1 这正是我脑海中想到的确切解决方案，经过更长时间的思考后，我并没有看到更简单的方法。 - Robert Gamble

我编辑了答案，使其适合页面而无需滚动条，并将 // 更改为 ''，这样更适合语法突出显示（它会认为 // 是一个注释）。 - Robert Gamble

看起来完美无缺...你能否编辑一下说明它的工作原理吗？ - frankodwyer

split/sort/join将字符串转换为字符数组，对其进行排序，并将排序后的结果转换回字符串。gsub用长度和运行中的第一个字符（在该运行中都相同）替换任何连续3个或更多个相同字符的情况。 - Robert Gamble

Answer 3

我没有找到一个优雅的解决方案。您可以使用“split”方法将字符转换为数组，但是一旦您对列表进行了排序，我就看不到一个漂亮的线性时间连接原语来返回字符串。令人惊讶。

顺便说一句，“游程编码几乎肯定是浪费时间”。除非我看到一些非常令人印象深刻的测量结果，否则我不认为值得考虑。如果避免游程编码，则可以对任何字符串进行重新排列，而不仅仅是字母字符串。如果您知道只有字母并试图节省空间，则可以将它们压缩为每个字母的5位。

---Irma Vep 编辑：其他帖子发现了我错过的“join”方法。好极了。

- Norman Ramsey

---

你可以使用 str.scan(/./) 或 str.split('') 来形成一个字符数组，对该数组进行排序，然后使用 String#join 将其重新连接在一起，尽管将其连接回字符串是不必要的。 - Zach Langley

+1 指出 RLE 可能无法节省太多空间。 - Sparr