3

这是一个场景，您试图在一个大文本文件中查找所有单词，其版本也在文件中。

通过“反转”，我的意思是给出一个单词“abc”，看看文件中是否有“cba”。文本文件包含大约 10,000,000 个单词。单词的长度不超过 1000。

我想出的想法是找到一个哈希来映射一个单词并将其还原到同一个键。并排序尊重关键。因此，现在您可以线性检查以找到所有可能符合条件的单词。

问题是：“找到这个哈希”。欢迎任何其他棘手的解决方案来解决这个问题。

如果我能找到一个散列来将字符串映射到一个键，我可以使用外部排序对它们进行排序并使字符串及其反转相邻。所以找到它们是微不足道的。

4

5 回答 5

3

最简单的散列是：任意散列（提供足够大的散列空间）！

假设您的字符串是“foo”。它的反面是“oof”。在某些任意顺序（例如字典顺序）中，“foo”出现在“oof”之前。现在散列以该顺序首先出现的字符串。

所以而不是

hash = fancyHash(string);

你做

std::string rstring(string.rbegin(), string.rend());
hash = (string < rstring) ? anyhash(string) : anyhash(rstring);

@HighPerformanceMark 建议的使用 linux 工具的一种方法：（文本是包含您的话的文件。它们可能在同一行，没关系）

rev text | tr "[:upper:]" "[:lower:]" | tr " " "\n" > rtext; rev rtext > rrtext; comm -12 <(sort -u rrtext) <(sort -u rtext);

解释：

rev反转文件，因此rev text输出反转 tr "[:upper:]" "[:lower:]"将所有内容转换为小写（可选。如果“Foo”不计为“oOf”的反转，请不要这样做） tr " " "\n"给每个单词一个单独的文件

在此之后，文件rtext在不同的行上包含小写（可选）单词。该文件中的每个单词都是 file 的倒序单词text。

rev rtext > rrtext再次反转以将小写的内容也变为原始内容，并将每个单词分隔在不同的行上。

comm -12 <(sort -u rrtext) <(sort -u rtext). 作为 的输入comm，我们给出了我们首先排序和重复的两个文本文件 ( -u)。选项抑制所有对第一个输入 ( ) 或第二个输入 ( )-12唯一的单词。因此，此命令的每个输出都存在于两个文件中。rrtextrtext

于 2013-09-17T13:42:27.583 回答
2

因此，如果您将所有单词读入 a map（或unordered_map，它通过哈希表实现），那么您可以遍历单词列表，并找到（使用map.find(the_word.reverse())- 如果返回一个有效单词，您有列表中的单词。否则，该单词没有反向变体。

于 2013-09-17T13:24:06.527 回答
2

对所有单词的列表进行排序（在程序中或通过 gnu shell 工具），获得所有反转单词的排序列表（相同）与列表相交（又名加入为 gnu 工具）

除了列表，程序当然也可以使用集合表示，尤其是哈希集（unordered_set）。但是，如果文件非常大，您可能会遇到内存问题，而 sort & join 可以基于磁盘工作。此外，哈希集对于计算交集并不是很好

关于您的解决方案：如果相同的单词包含两次，它也将具有相同的哈希并且似乎存在反转

于 2013-09-17T14:06:46.653 回答
2

阅读输入列表。对于每个单词，将两个单词写入输出列表，单词本身及其反转。对输出列表进行排序。反转出现在原始列表中的单词将在排序的输出列表中出现两次（在连续的位置），反转不在原始列表中的单词将只出现一次。

我认为您可以使用标准的 Linux 文件处理实用程序和一些管道在一行中完成此操作。例如

rev wordlist.txt > revlist.txt && cat wordlist.txt revlist.txt | sort | uniq -c

鉴于现代现成的排序例程的速度，我怀疑这可能会胜过更复杂的算法，并且具有更低（渐近）复杂度。但这只是一个猜测。

于 2013-09-17T13:35:47.760 回答
1

如果“cat”和“cat”出现在没有“tac”的同一个文件中，这是一个不会遇到问题的解决方案。

Create a HashSet to hold strings.

For each word w in the file

  Reverse w (call it revW)

  If HashSet contains revW

    Both w and revW appear in the file, add it to our results list.

  Regardless, Add w into the HashSet (we might see another revW later on)

从算法上讲，您只需读取文件一次，将每个单词反转一次，在哈希集中查找每个单词的反向一次，然后将每个单词添加到哈希集中。

所以这个算法是线性复杂的，假设 HashSet/HashFunction 提供恒定时间查找/插入。

（可选地对 HashSet 中的每个单词进行计数，以跟踪该单词出现的次数）。

因此，所有单词都会向前散列，但您只能反向查找它们。

于 2013-09-17T14:28:24.290 回答