Форум программистов, компьютерный форум, киберфорум
Наши страницы
C (Си)
Войти
Регистрация
Восстановить пароль
 
Operator_pls
0 / 0 / 0
Регистрация: 24.11.2017
Сообщений: 2
1

Алгоритм оптимального несовпадения

01.03.2019, 00:03. Просмотров 212. Ответов 0

Господа, нашел интересный (для меня) алгоритм точного поиска подстроки, который использует частотность букав. По ссылке:
Optimal mismatch algorithm description and C implementation

В конце страницы есть примеры двух фаз.

Хотел бы получить подробное объяснение по "Preprocessing phase", а именно о том, как заполняются таблицы (массивы). Желательно на русском, потому как в С не могу

Перевел статью более-менее точно, смотреть спойлер.


Кликните здесь для просмотра всего текста

Основные особенности
  • Разновидность алгоритма быстрого поиска;
  • Требует частотность символов;
  • Фаза предварительной обработки: http://www.cyberforum.ru/cgi-bin/latex.cgi?O({m}^{2}+\sigma) - временная сложность, http://www.cyberforum.ru/cgi-bin/latex.cgi?O(m+\sigma) - пространственная сложность;
  • Фаза поиска: http://www.cyberforum.ru/cgi-bin/latex.cgi?O(mn) временная сложность;

_____________________________________________________________________________________________________________

Описание
Сандей разработал алгоритм, в котором символы шаблона сканируются от наименее частого до наиболее частого. Это может привести к несоответствию в большинстве случаев и, таким образом, к быстрому сканированию всего текста. Но необходимо знать частоты каждого из символов алфавита.

Фаза предварительной обработки алгоритма оптимального несовпадения состоит в сортировке символов шаблона в порядке убывания их частот, а затем в построении функции быстрого поиска неправильных символов (см. Главу Алгоритм быстрого поиска) и функции смещения хорошего суффикса, адаптированной к порядку сканирования символов шаблона.

_____________________________________________________________________________________________________________

Реализация на С
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
typedef struct patternScanOrder {
   int loc;
   char c;
} pattern;
 
int freq[ASIZE];
 
/* Construct an ordered pattern from a string. */
void orderPattern(char *x, int m, int (*pcmp)(),
                  pattern *pat) {
   int i;
 
   for (i = 0; i <= m; ++i) {
      pat[i].loc = i;
      pat[i].c = x[i];
   }
   qsort(pat, m, sizeof(pattern), pcmp);
}
 
 
/* Optimal Mismatch pattern comparison function. */
int optimalPcmp(pattern *pat1, pattern *pat2) {
   float fx;
 
   fx = freq[pat1->c] - freq[pat2->c];
   return(fx ? (fx > 0 ? 1 : -1) :
               (pat2->loc - pat1->loc));
}
 
 
/* Find the next leftward matching shift for
   the first ploc pattern elements after a
   current shift or lshift. */
int matchShift(char *x, int m, int ploc,
               int lshift, pattern *pat) {
   int i, j;
 
   for (; lshift < m; ++lshift) {
      i = ploc;
      while (--i >= 0) {
         if ((j = (pat[i].loc - lshift)) < 0)
            continue;
         if (pat[i].c != x[j])
            break;
      }
      if (i < 0)
         break;
   }
   return(lshift);
}
 
 
/* Constructs the good-suffix shift table
   from an ordered string. */
void preAdaptedGs(char *x, int m, int adaptedGs[],
                  pattern *pat) {
   int lshift, i, ploc;
 
   adaptedGs[0] = lshift = 1;
   for (ploc = 1; ploc <= m; ++ploc) {
      lshift = matchShift(x, m, ploc, lshift, pat);
      adaptedGs[ploc] = lshift;
   }
   for (ploc = 0; ploc <= m; ++ploc) {
      lshift = adaptedGs[ploc];
      while (lshift < m) {
         i = pat[ploc].loc - lshift;
         if (i < 0 || pat[ploc].c != x[i])
            break;
         ++lshift;
         lshift = matchShift(x, m, ploc, lshift, pat);
      }
      adaptedGs[ploc] = lshift;
   }
}
 
 
/* Optimal Mismatch string matching algorithm. */
void OM(char *x, int m, char *y, int n) {
   int i, j, adaptedGs[XSIZE], qsBc[ASIZE];
   pattern pat[XSIZE];
 
   /* Preprocessing */
   orderPattern(x, m, optimalPcmp, pat);
   preQsBc(x, m, qsBc);
   preAdaptedGs(x, m, adaptedGs, pat);
 
   /* Searching */
   j = 0;
   while (j <= n - m) {
      i = 0;
      while (i < m && pat[i].c == y[j + pat[i].loc])
         ++i;
      if (i >= m)
         OUTPUT(j);
      j += MAX(adaptedGs[i],qsBc[y[j + m]]);
   }
}
_____________________________________________________________________________________________________________

Пример:

Выше расписана фаза предварительной обработки

Фаза поиска

0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.03.2019, 00:03
Ответы с готовыми решениями:

Алгоритм оптимального сложения
Нужно написать диплом на тему реализация алгоритма оптимального сложения на ПЛИС Нужна любая...

Алгоритм поиска оптимального пути.
Привет всем :) Вот заранее начал готовится к диплому, нашел ваш форум и понял что именно тут...

Алгоритм оптимального расположения на графе
Дан неориентированый граф. Необходимо вычислить, какие узлы отмечать, так, что бы расстояние до...

Алгоритм оптимального кодирования Хаффмена
Добрый день! Помогите, пожалуйста, написать алгоритм оптимального кодирования Хаффмена.

Алгоритм поиска оптимального сочетания
Уважаемы программисты, всех приветствую! Помогите плиз написать алгоритм, задачу задали, над...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.03.2019, 00:03

Реализовать алгоритм оптимального кодирования Хаффмана
Добрый день! Нужно реализовать алгоритма Хаффмана. Помогите, пожалуйста.

Алгоритм оптимального распараллеливания задач на несколько потоков
Имеем 4-ядерный процессор и 100 задач. Задачи разные по сложности - могут выполняться от 1 до 10...

Генетический алгоритм оптимального расположения файлов на диске
Добрый вечер. Не понимаю одну вещь. Есть набор последовательностей обращений к файлам на...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru