所有单词中最频繁的n-gram是什么？

Question

我发现了以下的编程面试问题:

挑战1：N-gram

N-gram是从给定单词中连续N个字符组成的序列。对于单词"pilot"，有三个3-gram："pil"、"ilo"和"lot"。 对于给定的一组单词和n-gram长度， 你的任务是：

• write a function that finds the n-gram that is the most frequent one among all the words
• print the result to the standard output (stdout)
• if there are multiple n-grams having the same maximum frequency please print the one that is the smallest lexicographically (the first one according to the dictionary sorting order)

请注意，您的函数将接收以下参数：

• text
    ○ which is a string containing words separated by whitespaces
• ngramLength
    ○ which is an integer value giving the length of the n-gram

数据限制

• the length of the text string will not exceed 250,000 characters
• all words are alphanumeric (they contain only English letters a-z, A-Z and numbers 0-9)

效率限制

• your function is expected to print the result in less than 2 seconds

例子 输入文本：“aaaab a0a baaab c”

输出 aaa ngram长度：3

解释

对于上述输入，按频率排序的3元组如下：

• "aaa" with a frequency of 3
• "aab" with a frequency of 2
• "a0a" with a frequency of 1
• "baa" with a frequency of 1

如果我只有一个小时解决问题，并选择使用C语言解决：是否实现哈希表来计算N元组的频率是个好主意？因为在C库中没有哈希表的实现...

如果是，我想通过使用具有有序链表的分离链接来实现哈希表。这些实现减少了解决问题所需的时间....

这是可能的最快选项吗？

谢谢!!!

- andrestoga

---

这是用于实际的编程面试吗？ - templatetypedef

你确定了二叉树（比如AVL）不能胜任这个任务吗？ - Iwillnotexist Idonotexist

你最多会被要求翻译3元组吗？只考虑字母数字字符，共有(26+26+10)^3=238328种可能的3元组，因此使用查找表似乎可行。 - Iwillnotexist Idonotexist

我会提前分配所需数量的桶，在单个数组中（因为您对文本长度有一个上限，所以这是可能的），并且只在哈希表中存储指向它们的指针。使用移动到前面/插入到后面的启发式方法可以使哈希表检索更快。最后对数组进行排序。实际上使用树会更慢。 - michaelmeyer

也许不是直接相关的，但仍然很有趣。 - phs

想一想，在1000个字符的文本中，有多少个3元组？ - Colonel Panic

Answer 1

如果实现效率是最重要的，并且您正在使用C语言，我建议初始化一个指针数组来存储字符串中n元组的起始位置，使用qsort函数按照它们所属的n元组对指针进行排序，然后循环遍历已排序的数组并计算出数值。

这样做应该执行得足够快，而且不需要编写任何复杂的数据结构。

- btilly

---

我所能想到的唯一比这更快的方法是使用偏移量而不是实际指针。假设64位（本机）指针，您可以使用4字节偏移量减少一半的内存。聪明的编码可能会将所需的18位压缩成2个字节以获得更多的空间。 - phs

@phs，排序的时间复杂度为O(n log(n))，而基于哈希表的解决方案则为O(n)。因此，这并不是最佳性能。这只是一种非常简单的方法。 - btilly

在小规模上，渐近极限的影响比硬件细节要小。我猜缓存行效率和所选择的哈希函数的细节会很重要。再次强调，这只是猜测。 - phs

@phs 我看不出为什么在哈希中跳转到一个随机桶比从区域中比较两个随机指针更有效地使用缓存。因此，哈希始终是一种胜利的选择。但是，如果您创建一个ngrams数组，然后对其进行排序（而不是使用指针），则可能会击败哈希。 - btilly

很棒的答案。排序后，您可以从较大的数组索引到较小的数组索引一次性地使用O(1)空间进行计数。 - גלעד ברקן

Answer 2

抱歉，我发了一篇关于Python的帖子，但这就是我会做的事情： 您可能会得到一些算法的想法。请注意，此程序可以解决更多数量级的单词。

from itertools import groupby

someText = "thibbbs is a test and aaa it may haaave some abbba reptetitions "
someText *= 40000
print len(someText)
n = 3

ngrams = []
for word in filter(lambda x: len(x) >= n, someText.split(" ")):
    for i in range(len(word)-n+1):
        ngrams.append(word[i:i+n])
        # you could inline all logic here
        # add to an ordered list for which the frequiency is the key for ordering and the paylod the actual word

ngrams_freq = list([[len(list(group)), key] for key, group in groupby(sorted(ngrams, key=str.lower))])

ngrams_freq_sorted = sorted(ngrams_freq, reverse=True)

popular_ngrams = []

for freq in ngrams_freq_sorted:
    if freq[0] == ngrams_freq_sorted[0][0]:
        popular_ngrams.append(freq[1])
    else:
        break

print "Most popular ngram: " + sorted(popular_ngrams, key=str.lower)[0]
# > 2560000
# > Most popular ngram: aaa
# > [Finished in 1.3s]**

- AlexanderBrevig

---

在我的测试中，维护一个ngram/count字典的速度是你的解决方案的两倍，并且代码更简单。 - btilly

我会期望两者都有，这就是为什么我在注释中提到它的原因。我已经在我的帖子中添加了一个C++的答案。我认为这是一个有趣的小问题。 - AlexanderBrevig

Answer 3

如果您不局限于C语言，我已经在大约10分钟内用Python编写了这个脚本，处理了一个包含265000个单词的1.5Mb文件，查找3元组仅需0.4秒（除了在屏幕上打印值之外）。测试使用的文本是詹姆斯·乔伊斯的《尤利西斯》，您可以在这里免费找到它https://www.gutenberg.org/ebooks/4300。单词分隔符包括空格和回车符\n。

import sys

text = open(sys.argv[1], 'r').read()
ngram_len = int(sys.argv[2])
text = text.replace('\n', ' ')
words = [word.lower() for word in text.split(' ')]
ngrams = {}
for word in words:
    word_len = len(word)
    if word_len < ngram_len:
        continue
    for i in range(0, (word_len - ngram_len) + 1):
        ngram = word[i:i+ngram_len]
        if ngram in ngrams:
            ngrams[ngram] += 1
        else:
            ngrams[ngram] = 1
ngrams_by_freq = {}
for key, val in ngrams.items():
        if val not in ngrams_by_freq:
                ngrams_by_freq[val] = [key]
        else:
                ngrams_by_freq[val].append(key)
ngrams_by_freq = sorted(ngrams_by_freq.items())
for key in ngrams_by_freq:
        print('{} with frequency of {}'.format(key[1:], key[0]))

- Andrea Tulimiero

Answer 4

那么这个问题的基本解决方案是：

1. 在字符串中找到所有n元组
2. 将所有重复项映射到一个新的数据结构中，该数据结构包含n元组及其出现次数

你可以在这里找到我的C++解决方案：http://ideone.com/MNFSis

给定：

const unsigned int MAX_STR_LEN = 250000;
const unsigned short NGRAM = 3;
const unsigned int NGRAMS = MAX_STR_LEN-NGRAM;
//we will need a maximum of "the length of our string" - "the length of our n-gram"
//places to store our n-grams, and each ngram is specified by NGRAM+1 for '\0'
char ngrams[NGRAMS][NGRAM+1] = { 0 };

然后，对于第一步 - 这是代码：

const char *ptr = str;
int idx = 0;
//notTerminated checks ptr[0] to ptr[NGRAM-1] are not '\0'
while (notTerminated(ptr)) { 
    //noSpace checks ptr[0] to ptr[NGRAM-1] are isalpha()
    if (noSpace(ptr)) {
        //safely copy our current n-gram over to the ngrams array
        //we're iterating over ptr and because we're here we know ptr and the next NGRAM spaces
        //are valid letters
        for (int i=0; i<NGRAM; i++) {
            ngrams[idx][i] = ptr[i];
        }
        ngrams[idx][NGRAM] = '\0'; //important to zero-terminate
        idx++;
    }
    ptr++;
}

此时，我们已经有了所有n-gram的列表。让我们找到最受欢迎的一个：

FreqNode head = { "HEAD", 0, 0, 0 }; //the start of our list

for (int i=0; i<NGRAMS; i++) {
    if (ngrams[i][0] == '\0') break;
    //insertFreqNode takes a start node, this where we will start to search for duplicates
    //the simplest description is like this:
    //  1 we search from head down each child, if we find a node that has text equal to
    //    ngrams[i] then we update it's frequency count
    //  2 if the freq is >= to the current winner we place this as head.next
    //  3 after program is complete, our most popular nodes will be the first nodes
    //    I have not implemented sorting of these - it's an exercise for the reader ;)
    insertFreqNode(&head, ngrams[i]);
}

//as the list is ordered, head.next will always be the most popular n-gram
cout << "Winner is: " << head.next->str << " " << " with " << head.next->freq << " occurrences" << endl

祝你好运！

- AlexanderBrevig

Answer 5

仅为娱乐，我编写了一个 SQL 版本（SQL Server 2012）：

if object_id('dbo.MaxNgram','IF') is not null
    drop function dbo.MaxNgram;
go

create function dbo.MaxNgram(
     @text      varchar(max)
    ,@length    int
) returns table with schemabinding as
return
    with 
    Delimiter(c) as ( select ' '),
    E1(N) as (
        select 1 from (values 
            (1),(1),(1),(1),(1),(1),(1),(1),(1),(1)
        )T(N)
    ),
    E2(N) as (
        select 1 from E1 a cross join E1 b
    ),
    E6(N) as (
        select 1 from E2 a cross join E2 b cross join E2 c
    ),
    tally(N) as (
        select top(isnull(datalength(@text),0))
             ROW_NUMBER() over (order by (select NULL))
        from E6
    ),
    cteStart(N1) as (
        select 1 union all
        select t.N+1 from tally t cross join delimiter 
            where substring(@text,t.N,1) = delimiter.c
    ),
    cteLen(N1,L1) as (
        select s.N1,
               isnull(nullif(charindex(delimiter.c,@text,s.N1),0) - s.N1,8000)
        from cteStart s
        cross join delimiter
    ),
    cteWords as (
        select ItemNumber = row_number() over (order by l.N1),
               Item       = substring(@text, l.N1, l.L1)
        from cteLen l
    ),
    mask(N) as ( 
        select top(@length) row_Number() over (order by (select NULL))
        from E6
    ),
    topItem as (
        select top 1
             substring(Item,m.N,@length) as Ngram
            ,count(*)                    as Length
        from cteWords   w
        cross join mask m
        where m.N     <= datalength(w.Item) + 1 - @length
          and @length <= datalength(w.Item) 
        group by 
            substring(Item,m.N,@length)
        order by 2 desc, 1 
    )
    select d.s
    from (
        select top 1 NGram,Length
        from topItem
    ) t
    cross apply (values (cast(NGram as varchar)),(cast(Length as varchar))) d(s)
;
go

当使用OP提供的示例输入调用时

set nocount on;
select s as [ ] from MaxNgram(
    'aaaab a0a baaab c aab'
   ,3
);
go

产生所期望的结果。

------------------------------
aaa
3

- Pieter Geerkens

Answer 6

这个问题有一个简单的Python解决方案

your_str = "aaaab a0a baaab c"
str_list = your_str.split(" ")
str_hash = {}
ngram_len = 3

for str in str_list:
    start = 0
    end = ngram_len
    len_word = len(str)
    for i in range(0,len_word):
        if end <= len_word :
            if str_hash.get(str[start:end]):              
                str_hash[str[start:end]] = str_hash.get(str[start:end]) + 1
            else:
                str_hash[str[start:end]] = 1
            start = start +1
            end = end +1
        else:
            break

keys_sorted =sorted(str_hash.items())
for ngram in sorted(keys_sorted,key= lambda x : x[1],reverse = True):
    print "\"%s\" with a frequency of %s" % (ngram[0],ngram[1])

- Vishnu R

Answer 7

你可以将三字母组转换为RADIX50代码。请参见http://en.wikipedia.org/wiki/DEC_Radix-50。

在radix50中，三字母组的输出值适合于16位无符号整数值。

然后，您可以使用基数编码的三字母组作为数组中的索引。

因此，您的代码应该像这样：

uint16_t counters[1 << 16]; // 64K counters

bzero(counters, sizeof(counters));

for(const char *p = txt; p[2] != 0; p++) 
  counters[radix50(p)]++;

此后，只需在数组中搜索最大值，并将索引解码为三元组即可。

我在实现Wilbur-Khovayko模糊搜索算法时使用了这个技巧，那是大约10年前的事情。

您可以在此处下载源代码: http://itman.narod.ru/source/jwilbur1.tar.gz。

- olegarch

---

这是不区分大小写的 A-Z、0-9、空格、美元符号、点和未定义字符。足以计算文本字符串的三元组。 - olegarch

但是您事先不知道ngramLength参数，这在很大程度上取决于n=3的事实。虽然这是三元组的巧妙解决方案。 - jlhonora

从radix50开始， 对于每个计数器c按降序排序 找到最频繁的起始项-> counters2 //现在唯一需要做的是检查是否有其他计数器中的某些项比counters中的下一个项大，并且比之前找到的本地最大值要大 如果（counters2中的最大值 > counters中的下一个项，并且大于之前找到的本地最大值）则返回RESULT 否则存储本地最大值，并继续处理下一项 - zubrabubra

Answer 8

您可以在O(nk)的时间内解决这个问题，其中n是单词数量，k是每个单词的平均n-gram数。

您的想法是正确的，哈希表是解决这个问题的好方法。

然而，由于您有限的编码时间，我建议使用开放地址法而不是链表。实现可能更简单：如果发生冲突，您只需沿着列表继续走。

此外，请确保为哈希表分配足够的内存：大约是预期n-gram数量的两倍即可。由于预期的n-gram数量小于等于250,000，因此500,000的哈希表应该足够了。

在编码速度方面，输入长度较短（250,000）使得排序和计数成为可行的选项。最快的方法可能是生成一个指向每个n-gram的指针数组，使用适当的比较器对数组进行排序，然后沿着数组走，跟踪出现最多的n-gram。

- Richard