N-грамм, который является наиболее частым среди всех слов

Если важна эффективность реализации и вы используете C, я бы инициализировал массив указателей на начало n-граммов в строке, использовал qsort для сортировки указателей в соответствии с n-граммами, частью которых они являются, а затем перебрать этот отсортированный массив и вычислить количество.

Это должно выполняться достаточно быстро, и нет необходимости кодировать какие-либо причудливые структуры данных.

Извините за публикацию 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]**

Итак, основной рецепт этой проблемы:

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-граммов. Давайте найдем самый популярный из них:

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

Удачи тебе!

Ради интереса я написал версию 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

Если вы не привязаны к C, я написал этот скрипт Python примерно за 10 минут, который обрабатывает файл размером 1,5 МБ, содержащий более 265 000 слов, ищущих 3 грамма за 0,4 ​​секунды. (кроме вывода значений на экран)
Для теста используется текст Улисс Джеймса Джойса, его можно бесплатно найти здесь https://www.gutenberg.org/ebooks/4300

Здесь оба разделителя слов space и возврат каретки \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]))

Вы можете преобразовать триграмму в код 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)]++;

После этого просто найдите максимальное значение в массиве и декодируйте индекс обратно в триграмму.

Я использовал этот трюк, когда реализовал алгоритм Уилбура-Ховайко для нечеткого поиска ~ 10 лет назад.

Вы можете скачать исходный код здесь: http://itman.narod.ru/source/jwilbur1.tar.gz.

Вы можете решить эту проблему за O (nk) времени, где n - количество слов, а k - среднее количество n-граммов на слово.

Вы правы, полагая, что хеш-таблица - хорошее решение проблемы.

Однако, поскольку у вас ограничено время для написания кода решения, я бы предложил вместо этого использовать открытую адресацию. связанного списка. Реализация может быть проще: если вы дойдете до столкновения, вы просто пройдете дальше по списку.

Кроме того, не забудьте выделить достаточно памяти для вашей хеш-таблицы: что-то примерно в два раза больше ожидаемого числа n-граммов должно быть в порядке. Поскольку ожидаемое количество n-граммов будет ‹= 250 000, хеш-таблицы 500 000 должно быть более чем достаточно.

Что касается скорости кодирования, небольшая длина ввода (250 000) делает возможной сортировку и подсчет. Самый быстрый способ - это, вероятно, сгенерировать массив указателей на каждую n-грамм, отсортировать массив, используя соответствующий компаратор, а затем пройтись по нему, отслеживая, какая n-грамм появляется больше всего.

Одно простое решение 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])