1

Тема: Генерація Nграм

Всім привіт. Можливо тема трохи неясно відображає суть, але постараюсь пояснити.
У мене є певна кількість значень.
Для прикладу: A B C D E
Тобто 5 значень.
Для них треба зегенерувати 3грами. На виходы маэ вийти така фішка:

Прихований текст

  ABC
  ABD
  ABE
  ACE
  ADE
  BCD
  BDE
  CDE 

Якщо будувати слово з 4х символів тоді на виході отримуємо таку штуку:

Прихований текст

  ABCD
  ABDE
  ACDE

Який алгоритм знаходження таких штук.

Тобто я маю 2 вхідні параметри. Масив елементів і довжина слова.
Дякую ;)

2

Re: Генерація Nграм

Ну ще перший варіант приблизно можна зрозуміти, а от другий щось, мені здається, незавершене. Варіант генерації для першого випадку в MySQL:

CREATE TABLE `tmp` (
    `id` VARCHAR(50) NULL DEFAULT NULL
);

insert into tmp (id) values('a'), ('b'), ('c'), ('d');

select * from tmp t1, tmp t2, tmp t3;

3

Re: Генерація Nграм

ktretyak - дякую, але вказаний вами спосіб не підходить. Він генерує щось на зразок цього
aaa
bbb
+ і інші)
У мене таких значень неможе бути)

4

Re: Генерація Nграм

std::next_permutation

5

Re: Генерація Nграм

2Koala Це на чому?

6

Re: Генерація Nграм

На С++ напевне. Але думаю тобі треба не всі розміщення, а лише ті в яких елементи йдуть в такому самому порядку, що й в оригінальній послідовності...

7

Re: Генерація Nграм

funivan написав:

ktretyak - дякую, але вказаний вами спосіб не підходить. Він генерує щось на зразок цього
aaa
bbb
+ і інші)
У мене таких значень неможе бути)

А слабо в кінці селекта дописати?

where t1.id <> t2.id and t2.id <> t3.id and t1.id <> t3.id

8

Re: Генерація Nграм

def ngrams(lst, n): # приймаємо елементи і кількість
    if len(lst) == n: # якщо потрібно вибрати таку саму кількість як їх є
        yield lst  # - вибираємо всі
        return
    if n == 1: # якщо потрібно вибрати один елемент
        for ngram in lst: # по черзі 
            yield ngram # повертаємо кожен
        return
    # і нарешті
    for i in range(len(lst) - n): # вибираємо один з перших елементів
        for ngram in ngrams(lst[i+1:], n - 1): # перебираємо усі (n-1)-грами в яких ми вже не можемо взяти перший елемент
            yield lst[i] + ngram # і повертаємо їх конкатенацію.

for ngram in ngrams('abcde', 3):
    print ngram

Вивід:
abc
abd
abe
acd
ace
bcd
bce

Якщо не зрозуміло що таке yield - уявіть собі просто що це додавання результату до масиву, який потім повернеться по закінченню роботи функції, або при зустрічі з return. :)

Хоча, щось мені здається що це неправильно працює для чотирьох елементів... :(

Подякували: koala, funivan2

9

Re: Генерація Nграм

Начебто звичайна рекурсія:

program Project1;

{$APPTYPE CONSOLE}

const
  StrLen = 3;

  procedure Gen(Symbols: string; Prefix: string = '');
  var
    i: Integer;
    InnerSymbols: string;
  begin
    if Length(Prefix) = StrLen - 1 then
    begin
      for i := 1 to Length(Symbols) do
        Writeln(Prefix + Symbols[i]);
    end
    else
      for i := 1 to Length(Symbols) do
      begin
        InnerSymbols := Copy(Symbols, i + 1, Length(Symbols) - i);
        Gen(InnerSymbols, Prefix + Symbols[i]);
      end;
  end;

begin
  Gen('ABCDE');
  Readln;
end.

10

Re: Генерація Nграм

Torbins у вас не вказується довжина елементів які необхідно генерити, наскільки я бачу ;)

Всім дякую, вікіпедія як завжди на висоті )

11

Re: Генерація Nграм

funivan
Задана константою StrLen.
І скиньте посилання на вікіпедію, цікаво глянути, які там варіанти.

12

Re: Генерація Nграм

https://uk.wikipedia.org/wiki/%D0%A0%D0 … A%D0%B0%29

13

Re: Генерація Nграм

Тю, так там же з повторами, а у вас у прикладах явно комбінація.