1. 1. Хакасский государственный университет им. Н.Ф. Катанова Структуры и алгоритмы обработки данных Лекция: Поиск подстрок. Николай Гребенщиков, www.grebenshikov.ru
  2. 2. Задачи на строках Основное приложение: вычислительная молекулярная био- логия (расшифровка ДНК). Поиск внутренних паттернов. Например, построение пре- фиксного дерева. Поиск частных паттернов. Например, поиск подстроки, растояния преобразования, наибольшей общей подпосле- довательности, совпадения с регулярным выражением. Поиск характеристических паттернов. Например, поиск кратных подстрок. 1
  3. 3. Поиск подстрок Дано: Текст в виде массива T и образец в виде массива P , где m ≤ n. Элементы массивов P и T - символы из конечного алфавита Σ. Говорят, что P встречается в T со сдвигом s, если 0 ≤ s ≤ n − m и T = P . Найти: Все допустимые сдвиги с которыми образец P встре- чается в тексте T . 2
  4. 4. Терминология Σ∗ - множество всех строк конечной длины, образованных с помощью символов алфавита Σ. - пустая строка. xy - конкатенация двух строк. w < x - w является префиксом строки x, то есть ∃y ∈ Σ∗, что x = wy. w = x - w является суффиксом строки x, то есть ∃y ∈ Σ∗, что x = yw. 3
  5. 5. Лемма о перекрывающихся суффиксах Пусть x, y, z - строки, для которых выполняются соотноше- ния x = z и y = z. Если |x| ≥ |y|, то x = y. Если |x| ≤ |y|, то y = x. Если |x| = |y|, то x = y. 4
  6. 6. Простейший алгоритм поиска подстрок NaiveStringMatcher(T, P) 1 n ← length 2 m ← length 3 for s ← 0 to n − m 4 do if P = T 5 then print(s) 5
  7. 7. Простейший алгоритм поиска подстрок 6
  8. 8. Анализ - простейшего алгоритма поиска подстрок Наихудший случай: T = an, P = am T (n) = Θ((n − m + 1)m) При m = n/2 T (n) = Θ(n2) 7
  9. 9. Алгоритм Рабина-Карпа Идея: использовать хэш-функцию опеределенную на множе- стве строк. h(S) = (S[k] + d(S + . . . + d(S + dS) . . .))mod q, где d - основание системы, q - модуль. 8
  10. 10. Алгоритм Рабина-Карпа h(P ) - хэш образца. {s: h(P ) = h(T ) ∧ 0 ≥ s ≥ n − m} - множество до- пустимых сдвигов. Обозначим ts = h(T ), тогда ts+1 = (d(ts − T g) + T ) mod q, где g ≡ dm−1(mod q) 9
  11. 11. Алгоритм Рабина-Карпа 10
  12. 12. Алгоритм Рабина-Карпа 11
  13. 13. Проблема алгоритма Рабина-Карпа Из равества h(P) = ts не следует, что P = T . Решение проверить сдвиг s посимвольным сравнением. 12
  14. 15. Анализ алгоритма Рабина-Карпа В наихудшем случае T (n, m) = Θ(m) + Θ((n − m + 1)m). Почему? В общем случае T (n, m) = O(n) + O(m(v + n/q)), где v - ко- личество допустимых сдвигов и q - модуль хэш-функции. Если v = O(1) ∧ q ≥ m ⇒ T (n, m) = O(m + n) = O(n), так как n≥m 14
  15. 16. Конечные автоматы M = (Q, q0, A, Σ, δ) Q - конечное множество состояний, q0 ∈ Q - начальное состояние, A ⊆ Q - конечное множество допустимых состояний, Σ - конечный входной алфавит, δ - функция переходов Q × Σ → Q. 15
  16. 17. Конечные автоматы φ - функция конечного состояния. φ() = q0 φ(wa) = δ(φ(w), a) для w ∈ Σ∗, a ∈ Σ 16
  17. 18. Конечный автомат для поиска подстрок σ(x) = max{k: Pk = x}, где Pk < P ∧ |Pk | = k - суффиксная функция Пример, P = ab, σ() = 0, σ(ccaca) = 1, σ(ccab) = 2. Правила построения автомата: 1. Q = {0, 1, . . . m}, q0 = 0, A = m 2. δ(q, a) = σ(Pq a) 17
  18. 19. Конечный автомат для образца P = ababaca 18
  19. 20. Алгоритм поиска подстроки с помощью конечного ав- томата 19
  20. 21. Алгоритм вычисления функции переходов 20
  21. 22. Анализ применения конечных автоматов для поиска под- строки Вычисление функции переходов - T (n, m) = O(m3|Σ|). Суще- ствуют алгоритмы - T (n, m) = O(m|Σ|) Поиск подстроки - T (n, m) = Θ(n) 21
  22. 23. На семинар и рефераты Поиск наибольшей общей последовательности. Алгоритмы поиска подстрок: Кнута-Морриса-Пратта, Бойера- Мура, Демелки-Бейза-Ятса-Гоннета, Бойера-Мура-Хоспула, Бойера-Мура-Санди, Бойера-Мура-Гелила. Алгоритмы вычисления растояния ммежду строками: Вагнера- Фишера, Хешберга, Ханта-Шиманского, Укконена-Майерса. 22
  23. 24. На семинар и рефераты Алгоритмы для поиска по регулярным выражениям. Алгоритмы вычисления периодичности: Крочемора, Мейна- Лоренца, Колпакова-Кучерова. Алгоритмы построения суффиксных деревьев: Укконена, Вайнера, Мак-Крейга. 23
  24. 25. Список литературы Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгорит- мы: построение и анализ, 2-е издание. - М. : Издатель- ский дом “Вильямс”, 2007. сс.1017-1046. Смит, Билл. Методы и алгоритмы вычислений на стро- ках. - М.: ООО “И.Д. Вильямс”, 2006. Гасфилд, Дэн. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. - СПб.: Невский Диалект; БХВ-Петербург, 2003. 24

Суффиксный автомат (или ориентированный ациклический граф слов ) — это мощная структура данных, которая позволяет решать множество строковых задач.

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

На интуитивном уровне, суффиксный автомат можно понимать как сжатую информацию обо всех подстроках данной строки. Впечатляющим фактом является то, что суффиксный автомат содержит всю информацию в настолько сжатом виде, что для строки длины он требует лишь памяти. Более того, он может быть построен также за время (если мы считаем размер алфавита константой; в противном случае — за время ).

Исторически , впервые линейность размера суффиксного автомата была открыта в 1983 г. Blumer и др., а в 1985 — 1986 гг. были представлены первые алгоритмы его построения за линейное время (Crochemore, Blumer и др.). Более подробно — см. список литературы в конце статьи.

На английском языке суффиксный автомат называется "suffix automaton" (во множественном числе — "suffix automata"), а ориентированный ациклический граф слов — "directed acyclic word graph" (или просто "DAWG").

Определение суффиксного автомата

Определение. Суффиксным автоматом для данной строки называется такой минимальный детерминированный конечный автомат, который принимает все суффиксы строки .

Расшифруем это определение.

Простейшие свойства суффиксного автомата

Простейшим, и вместе с тем важнейшим свойством суффиксного автомата является то, что он содержит в себе информацию обо всех подстроках строки . А именно, любой путь из начального состояния , если мы выпишем метки дуг вдоль этого пути, образует обязательно подстроку строки . И наоборот, любой подстроке строки соответствует некоторый путь, начинающийся в начальном состоянии .

В целях упрощения объяснений, мы будем говорить, что подстроке соответствует тот путь из начального состояния, метки вдоль которого образуют эту подстроку. И наоборот, мы будем говорить, что любому пути соответствует та строка, которую образуют метки его дуг.

В каждое состояние суффиксного автомата ведёт один или несколько путей из начального состояния. Будем говорить, что состоянию соответствует набор строк, соответствующих всем этим путям.

Примеры построенных суффиксных автоматов

Приведём примеры суффиксных автоматов, построенных для нескольких простых строк.

Начальное состояние мы будем обозначать здесь через , а терминальные состояния — отмечать звёздочкой.

Для строки :

Для строки :

Для строки :

Для строки :

Для строки :

Для строки :

Для строки :

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

Позиции окончаний , их свойства и связь с суффиксным автоматом

Рассмотрим любую непустую подстроку строки . Тогда назовём множеством окончаний множество всех позиций в строке , в которых оканчиваются вхождения строки .

Мы будем называть две подстроки и -эквивалентными, если их множества окончаний совпадают: . Таким образом, все непустые подстроки строки можно разбить на несколько классов эквивалентности соответственно их множествам .

Оказывается, что в суффиксном автомате -эквивалентным подстрокам соответствует одно и то же состояние . Иными словами, число состояний в суффиксном автомате равно количеству классов -эквивалентности среди всех подстрок, плюс одно начальное состояние. Каждому состоянию суффиксного автомата соответствуют одна или несколько подстрок, имеющих одно и то же значение .

Это утверждение мы примем как аксиому , и опишем алгоритм построения суффиксного автомата, исходя из этого предположения — как мы затем увидим, все требуемые свойства суффиксного автомата, кроме минимальности, будут выполнены. (А минимальность следует из теоремы Nerode — см. список литературы.)

Приведём также несколько простых, но важных утверждений касательно значений .

Лемма 1 . Две непустые подстроки и () являются -эквивалентными тогда и только тогда, когда строка встречается в строке только в виде суффикса строки .

Доказательство практически очевидно. В одну сторону: если и имеют одинаковые позиции окончаний вхождения, то является суффиксом , и она присутствует в только в виде суффикса . В обратную сторону: если является суффиксом и входит только как этот суффикс, то их значения равны по определению.

Лемма 2 . Рассмотрим две непустые подстроки и (). Тогда их множества либо не пересекаются, либо целиком содержится в , причём это зависит от того, является суффиксом или нет:

Доказательство. Предположим, что множества и имеют хотя бы один общий элемент. Тогда это означает, что строки и оканчиваются в одном и том же месте, т.е. — суффикс . Но тогда каждое вхождение строки содержит на своём конце вхождение строки , что и означает, что его множество целиком вкладывается в множество .

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

Доказательство.

Зафиксируем некоторый класс -эквивалентности. Если он содержит только одну строку, то корректность леммы очевидна. Пусть теперь количество строк больше одной.

Согласно лемме 1, две различные -эквивалентные строки всегда таковы, что одна является собственным суффиксом другой. Следовательно, в одном классе -эквивалентности не может быть строк одинаковой длины.

Обозначим через длиннейшую, а через — кратчайшую строку в данном классе эквивалентности. Согласно лемме 1, строка является собственным суффиксом строки . Рассмотрим теперь любой суффикс строки с длиной в отрезке , и покажем, что он содержится в этом же классе эквивалентности. В самом деле, этот суффикс может входить в только в виде суффикса строки (поскольку более короткий суффикс входит только в виде суффикса строки ). Следовательно, согласно лемме 1, этот суффикс -эквивалентен строке , что и требовалось доказать.

Суффиксные ссылки

Рассмотрим некоторое состояние автомата . Как мы теперь знаем, состоянию соответствует некоторый класс строк с одинаковыми значениями , причём если мы обозначим через длиннейшую из этих строк, то все остальные будут суффиксами .

Также мы знаем, что первые несколько суффиксов строки (если мы рассматриваем суффиксы в порядке убывания их длины) содержатся в том же самом классе эквивалентности, а все остальные суффиксы (как минимум, пустой суффикс) — в каких-то других классах. Обозначим через первый такой суффикс — в него мы и проведём суффиксную ссылку.

Здесь мы считаем, что начальному состоянию соответствует отдельный класс эквивалентности (содержащий только пустую строку), и полагаем .

Доказательство. Рассмотрим произвольное состояние . Суффиксная ссылка ведёт из него в состояние, которому соответствуют строки строго меньшей длины (это следует из определения суффиксной ссылки и из леммы 3). Следовательно, двигаясь по суффиксным ссылкам, мы рано или поздно придём из состояния в начальное состояние , которому соответствует пустая строка.

Лемма 5 . Если мы построим из всех имеющихся множеств дерево (по принципу "множество-родитель содержит как подмножества всех своих детей"), то оно будет совпадать по структуре с деревом суффиксных ссылок.

Доказательство.

То, что из множеств можно построить дерево, следует из леммы 2 (о том, что любые два множества либо не пересекаются, либо одно содержится в другом).

Рассмотрим теперь произвольное состояние и его суффиксную ссылку . Из определения суффиксной ссылки и из леммы 2 следует:

что вкупе с предыдущей леммой и доказывает наше утверждение: дерево суффиксных ссылок по сути своей есть дерево вкладывающихся множеств .

Приведём пример дерева суффиксных ссылок в суффиксном автомате, построенном для строки :

Промежуточный итог

Перед тем, как приступить к самому алгоритму, систематизируем накопленные выше знания, и введём пару вспомогательных обозначений.

Алгоритм построения суффиксного автомата за линейное время

Приступим к описанию самого алгоритма. Алгоритм будет онлайновым , т.е. будет добавлять по одному символу строки , перестраивая соответствующим образом текущий автомат.

Чтобы достичь линейного потребления памяти, в каждом состоянии мы будем хранить только значение , и список переходов из этого состояния. Метки терминальных состояний мы поддерживать не будем (мы покажем, как расставить эти метки после построения суффиксного автомата, если имеется необходимость в них).

Изначально автомат состоит из единственного состояния , которое мы условимся считать нулевым состоянием (остальные состояния будут получать номера ). Присвоим этому состоянию , а значению присвоим для удобства (означающее ссылку на фиктивное, несуществующее состояние).

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

  • Пусть — это состояние, соответствующее всей текущей строке до добавления символа . (Изначально , а после добавления каждого символа мы будем менять значение .)
  • Создадим новое состояние , проставив ему . Значение пока считаем неопределённым.
  • Сделаем такой цикл: изначально мы стоим в состоянии ; если из него нет перехода по букве , то добавляем этот переход по букве в состояние , и затем переходим по суффиксной ссылке, снова проверяя — если нет перехода, то добавляем. Если в какой-то момент случится, что такой переход уже есть, то останавливаемся — и обозначим через номер состояния, на котором это произошло.
  • Если ни разу не случилось, что переход по букве уже имелся, и мы так и дошли до фиктивного состояния (в которое мы попали по суффиксной ссылке из начального состояния ), то мы можем просто присвоить и выйти.
  • Допустим теперь, что мы остановились на некотором состоянии , из которого уже был переход по букве . Обозначим через то состояние, куда ведёт этот имеющийся переход.
  • Теперь у нас два случая в зависимости от того, или нет.
  • Если , то мы можем просто присвоить и выйти.
  • В противном случае, всё несколько сложнее. Необходимо произвести "клонирование" состояния : создать новое состояние , скопировав в него все данные из вершины (суффиксную ссылку, переходы), за исключением значения : надо присвоить .

    После клонирования мы проводим суффиксную ссылку из в это состояние , также перенаправляем суффиксную ссылку из в .

    Наконец, последнее, что мы должны сделать — это пройтись от состояния по суффиксным ссылкам, и для каждого очередного состояния проверять: если имелся переход по букве в состояние , то перенаправлять его в состояние (а если нет, то останавливаться).

  • В любом случае, чем бы ни закончилось выполнение этой процедуры, мы в конце обновляем значение , присваивая ему .

Если нам также нужно знать, какие вершины являются терминальными , а какие — нет, то мы можем найти все терминальные вершины после построения суффиксного автомата для всей строки. Для этого рассмотрим состояние, соответствующее всей строке (оно, очевидно, у нас сохранено в переменной ), и будем идти по его суффиксным ссылкам, пока не дойдём до начального состояния, и помечать каждое пройденное состояние как терминальное. Легко понять, что тем самым мы пометим состояния, соответствующие всем суффиксам строки , что нам и требовалось.

В следующем разделе мы подробно рассмотрим каждый шаг алгоритма и покажем его корректность .

Здесь же лишь отметим, что из алгоритма видно, что добавление одного символа приводит к добавлению одного или двух состояний в автомат. Таким образом, линейность числа состояний очевидна.

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

Доказательство корректности алгоритма

  • Назовём переход сплошным , если . В противном случае, т.е. когда , переход будем называть несплошным .

    Как можно увидеть из описания алгоритма, сплошные и несплошные переходы приводят к разным ветвям алгоритма. Сплошные переходы называются так потому, что, появившись впервые, они больше никогда не будут меняться. В противоположность им, несплошные переходы могут измениться при добавлении новых букв к строке (измениться может конец дуги-перехода).

  • Во избежание неоднозначностей, под строкой мы будем подразумевать строку, для которой был построен суффиксный автомат до добавления текущего символа .
  • Алгоритм начинается с того, что мы создаём новое состояние , которому будет соответствовать вся строка . Понятно, почему мы обязаны создать новое состояние — т.к. вместе с добавлением нового символа возникает новый класс эквивалентности — это класс строк, оканчивающихся на добавляемом символе .
  • После создания нового состояния алгоритм проходится по суффиксным ссылкам, начиная с состояния, соответствующего всей строке , и пытается добавить переход по символу в состояние . Тем самым, мы приписываем к каждому суффиксу строки символ . Но добавлять новые переходы мы можем только в том случае, если они не будут конфликтовать с уже имеющимися, поэтому, как только мы встретим уже имеющийся переход по символу , мы сразу же обязаны остановиться.
  • Самый простой случай — если мы так и дошли до фиктивного состояния , добавив везде по новому переходу вдоль символа . Это означает, что символ в строке ранее не встречался. Мы успешно добавили все переходы, осталось только проставить суффиксную ссылку у состояния — она, очевидно, должна быть равна , поскольку состоянию в данном случае соответствуют все суффиксы строки .
  • Второй случай — когда мы наткнулись на уже имеющийся переход . Это означает, что мы пытались добавить в автомат строку (где — некоторый суффикс строки , имеющий длину ), а эта строка уже была ранее добавлена в автомат (т.е. строка уже входит как подстрока в строку ). Поскольку мы предполагаем, что автомат для строки построен корректно, то новых переходов мы больше добавлять не должны.

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

  • Итак, по одному из возможных сценариев, переход оказался сплошным, т.е. . В этом случае всё просто, никакого расщепления производить не надо, и мы просто проводим суффиксную ссылку из состояния в состояние .
  • Другой, более сложный вариант — когда переход несплошной, т.е. >. Это означает, что состоянию соответствует не только нужная нам подстрока длины , но также и подстроки большей длины. Нам ничего не остаётся, кроме как произвести "расщепление" состояния : разбить отрезок строк, соответствующих ей, на два подотрезка, так что первый будет заканчиваться как раз длиной .

    Как производить это расщепление? Мы "клонируем" состояние , делая его копию с параметром . Мы копируем в из все переходы, поскольку мы не хотим никоим образом менять пути, проходившие через . Суффиксную ссылку из мы ведём туда, куда вела старая суффиксная ссылка из , а ссылку из направляем в .

    После клонирования мы проводим суффиксную ссылку из в — то, ради чего мы и производили клонирование.

    Остался последний шаг — перенаправить некоторые входящие в переходы, перенаправив их на . Какие именно входящие переходы надо перенаправить? Достаточно перенаправить только переходы, соответствующие всем суффиксам строки , т.е. нам надо продолжить двигаться по суффиксным ссылкам, начиная с вершины , и до тех пор, пока мы не дойдём до фиктивного состояния или не дойдём до состояния, переход из которого ведёт в состояние, отличное от .

Доказательство линейного числа операций

Во-первых, сразу оговоримся, что мы считаем размер алфавита константой . Если это не так, то говорить о линейном времени работы не получится: список переходов из одной вершины надо хранить в виде сбалансированного дерева, позволяющего быстро производить операции поиска по ключу и добавления ключа. Следовательно, если мы обозначим через размер алфавита, то асимптотика алгоритма составит при памяти. Впрочем, если алфавит достаточно мал, то можно, пожертвовав памятью, избежать сбалансированных списков, а хранить переходы в каждой вершине в виде массива длины (для быстрого поиска по ключу) и динамического списка (для быстрого обхода всех имеющихся ключей). Тем самым мы достигнем во времени работы алгоритма, но ценой потребления памяти.

Если мы рассмотрим все части алгоритма, то он содержит три места, линейная асимптотика которых не очевидна:

Воспользуемся известным фактом, что размер суффиксного автомата (как по числу состояний, так и по числу переходов) линеен . (Доказательством линейности по числу состояний является сам алгоритм, а доказательство линейности по числу переходов мы приведём ниже, после реализации алгоритма.).

Тогда очевидна линейная суммарная асимптотика первого и второго места : ведь каждая операция здесь добавляет в автомат один новый переход.

Осталось оценить суммарную асимптотику в третьем месте — в том, где мы перенаправляем переходы, ведущие в , на . Обозначим . Это суффикс строки , и с каждой итерацией его длина убывает — а, значит, и позиция как суффикса строки монотонно возрастает с каждой итерацией. При этом, если перед первой итерацией цикла соответствующая строка была на глубине () от (если считать глубиной число суффиксных ссылок, которые надо пройти), то после последней итерации строка станет -ой суффиксной ссылкой на пути от (которое станет новым значением ).

Таким образом, каждая итерация этого цикла приводит к тому, что позиция строки как суффикса всей текущей строки будет монотонно увеличиваться. Следовательно, всего этот цикл не мог отработать более итераций, что и требовалось доказать .

(Стоит заметить, что аналогичные аргументы можно использовать и для доказательства линейности работы первого места, вместо ссылки на доказательство линейности числа состояний.)

Реализация алгоритма

Вначале опишем структуру данных, которая будет хранить всю информацию о конкретном переходе (, , список переходов). При необходимости сюда можно добавить флаг терминальности, а также другую требуемую информацию. Список переходов мы храним в виде стандартного контейнера , что позволяет достичь суммарно памяти и времени на обработку всей строки.

struct state { int len, link; map< char ,int > next; } ;

Сам суффиксный автомат будем хранить в виде массива этих структур . Как доказывается в следующем разделе, если — это максимально возможная в программе длина строки, то достаточно завести память под состояний. Также мы храним переменную — состояние, соответствующее всей строке на данный момент.

const int MAXLEN = 100000 ; state st[ MAXLEN* 2 ] ; int sz, last;

Приведём функцию, инициализирующую суффиксный автомат (создающую автомат с единственным начальным состоянием):

void sa_init() { sz = last = 0 ; st[ 0 ] .len = 0 ; st[ 0 ] .link = - 1 ; ++ sz; /* // этот код нужен, только если автомат строится много раз для разных строк: for (int i=0; i }

Наконец, приведём реализацию основной функции — которая добавляет очередной символ в конец текущей строки, перестраивая соответствующим образом автомат:

void sa_extend (char c) { int cur = sz++ ; st[ cur] .len = st[ last] .len + 1 ; int p; for (p= last; p! = - 1 && ! st[ p] .next .count (c) ; p= st[ p] .link ) st[ p] .next [ c] = cur; if (p == - 1 ) st[ cur] .link = 0 ; else { int q = st[ p] .next [ c] ; if (st[ p] .len + 1 == st[ q] .len ) st[ cur] .link = q; else { int clone = sz++ ; st[ clone] .len = st[ p] .len + 1 ; st[ clone] .next = st[ q] .next ; st[ clone] .link = st[ q] .link ; for (; p! = - 1 && st[ p] .next [ c] == q; p= st[ p] .link ) st[ p] .next [ c] = clone; st[ q] .link = st[ cur] .link = clone; } } last = cur; }

Как уже упоминалось выше, если пожертвовать памятью (до , где — размер алфавита), то можно достичь времени построения автомата даже для любых — но для этого придётся в каждом состоянии хранить массив размера (для быстрого поиска перехода по нужной букве) и список всех переходов (для быстрого обхода или копирования всех переходов).

Дополнительные свойства суффиксного автомата

Число состояний

Число состояний в суффиксном автомате, построенном для строки длины , не превышает (для ).

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

Однако эту оценку легко показать и без знания алгоритма . Вспомним о том, что число состояний равно количеству различных значений множеств . Кроме того, эти множества образуют дерево по принципу "вершина-родитель содержит в себе как подмножества всех детей". Рассмотрим это дерево, и немного преобразуем его: пока в нём есть внутренняя вершина с одним сыном, то это означает, что этого сына не содержит как минимум одно число из родителя; тогда создадим виртуальную вершину с , равным этому числу, и привесим этого сына к родителю. В итоге мы получим дерево, в котором каждая внутренняя вершина имеет степень больше единицы, а число листьев не превосходит . Следовательно, всего в таком дереве не более вершины.

Итак, мы показали эту оценку независимо, без знания алгоритма.

Интересно заметить, что эта оценка неулучшаема, т.е. существует тест, на котором она достигается . Этот тест выглядит таким образом:

При обработке этой строки на каждой итерации, начиная с третьей, будет происходить расщепление состояния, и, тем самым, будет достигаться оценка .

Число переходов

Число переходов в суффиксном автомате, построенном для строки длины , не превышает (для ).

Докажем это.

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

Оценим теперь число несплошных переходов. Рассмотрим каждый несплошной переход; пусть текущий переход — это переход по символу . Поставим ему в соответствие строку , где строка соответствует длиннейшему пути из начального состояния в , а — длиннейшему пути из в какое-либо терминальное состояние. С одной стороны, все такие строки для всех несплошных переходов будут различными (поскольку строки и образованы только сплошными переходами). С другой стороны, каждая из таких строк , по определению терминального состояния, будет суффиксом всей строки . Поскольку непустых суффиксов у строки всего штук, и к тому же вся строка среди этих строк не могла содержаться (т.к. всей строке соответствует путь из сплошных рёбер), то общее число несплошных переходов не превосходит .

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

Интересно отметить, что также существует тест, на котором эта оценка достигается :

Связь с суффиксным деревом. Построение суффиксного дерева по суффиксному автомату и наоборот

Докажем две теоремы, устанавливающие взаимную связь между суффиксным автоматом и суффиксным деревом .

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

Для удобства введём обозначения: — это строка , записанная в обратном порядке, — это суффиксный автомат, построенный для строки , — это суффиксное дерево строки .

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

Теорема 1 . Дерево, образованное суффиксными ссылками в , является суффиксным деревом .

Теорема 2 . — это граф расширяющих ссылок суффиксного дерева . Кроме того, сплошные рёбра в — это инвертированные суффиксные ссылки в .

Эти две теоремы позволяют по одной из структур (суффиксному дереву или суффиксному автомату) построить другую за время — эти два простых алгоритма будут рассмотрены нами ниже в теоремах 3 и 4.

В целях наглядности, приведём суффиксный автомат с его деревом суффиксных ссылок и соответствующее суффиксное дерево для инвертированной строки. Для примера возьмём строку .

И его дерево суффиксных ссылок (для наглядности мы подписываем каждое состояние его -строкой):

:

Лемма . Следующие три утверждения эквивалентны для любых двух подстрок и :

Доказательство её довольно очевидно: если начала вхождений двух строк совпадают, то одна строка является префиксом другой, а, значит, одна строка лежит в суффиксном дереве на пути другой строки.

Доказательство теоремы 1 .

В терминах инвертированной строки это означает, что суффиксная ссылка ведёт в такой длиннейший префикс строки, соответствующей состоянию , чтобы этому префиксу соответствовало отдельное состояние . Иными словами, суффиксная ссылка ведёт в предка вершины в суффиксном дереве, что и требовалось доказать.

Доказательство теоремы 2 .

Состояния суффиксного автомата соответствуют вершинам суффиксного дерева.

Рассмотрим произвольный переход в суффиксном автомате . Наличие этого перехода означает, что — это такое состояние, класс эквивалентности которого содержит подстроку . В инвертированной строке это означает, что это такое состояние, которому соответствует подстрока, от которой (в тексте ) совпадает с от подстроки .

Это как раз и означает, что:

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

Теорема полностью доказана.

Теорема 3 . Имея суффиксный автомат , можно за время построить суффиксное дерево .

Теорема 4 . Имея суффиксное дерево , можно за время построить суффиксный автомат .

Доказательство теоремы 3 .

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

Согласно теореме 1, рёбра в дереве образуются как инвертированные суффиксные ссылки, и дуговые метки можно найти, исходя из разности состояний, и дополнительно зная для каждого состояния автомата один любой элемент его множества (этот один элемент множества можно поддерживать при построении автомата).

Таким образом, за время мы можем построить суффиксное дерево вместе с суффиксными ссылками в нём.

(Если мы считаем размер алфавита не константой, то на всё перестроение потребуется время .)

Доказательство теоремы 4 .

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

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

Во-первых, заметим, что часть этих расширяющих ссылок получаются непосредственно из суффиксных ссылок в дереве. В самом деле, если для любой вершины мы рассмотрим её суффиксную ссылку , то это означает, что надо провести расширяющую ссылку из в по первому символу строки, соответствующей вершине .

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

Этот процесс отработает за время , если мы считаем размер алфавита константным.

Таким образом, описанный алгоритм за время строит суффиксный автомат по суффиксному дереву для инвертированной строки.

(Если же мы считаем, что размер алфавита — также переменная величина, то асимптотика увеличится до .)

Применения при решении задач

Ниже мы рассмотрим, какие задачи можно решать с помощью суффиксного автомата.

Проверка вхождения

Условие . Дан текст , и поступают запросы в виде: дана строка , требуется проверить, входит или нет строка в текст как подстрока.

Асимптотика . Препроцессинг и на один запрос.

Решение . Построим суффиксный автомат по тексту за время .

Как теперь отвечать на один запрос. Пусть текущее состояние — это переменная , изначально она равна начальному состоянию . Будем идти по символам строки , соответствующим образом делая переход из текущего состояния в новое состояние. Если в какой-то момент случилось, что перехода из текущего состояния по нужному символу не оказалось — то ответ на запрос "нет". Если же мы смогли обработать всю строку , то ответ на запрос "да".

Понятно, что это будет работать за время . Более того, алгоритм фактически ищет длину наидлиннейшего префикса , встречающегося в тексте — и если входные образцы таковы, что эти длины маленькие, то и алгоритм будет работать значительно быстрее, не обрабатывая всю строку целиком.

Количество различных подстрок

Условие . Дана строка . Требуется узнать количество различных её подстрок.

Асимптотика . .

Решение . Построим суффиксный автомат по строке .

В суффиксном автомате любой подстроке строки соответствует какой-то путь в автомате. Поскольку повторяющихся строк в автомате быть не может, то ответ на задачу — это количество различных путей в автомате, начинающихся в начальной вершине .

Учитывая, что суффиксный автомат представляет собой ациклический граф, количество различных путей можно считать в нём с помощью динамического программирования.

А именно, пусть — это количество различных путей, начинающихся с состояния (включая путь длины ноль). Тогда верно:

т.е. можно выразить как сумму ответов по всевозможным переходам из состояния .

Ответом на задачу будет значение (единица отнимается, чтобы не учитывать пустую подстроку).

Суммарная длина различных подстрок

Условие . Дана строка . Требуется узнать суммарную длину всех различных её подстрок.

Асимптотика . .

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

т.е. мы берём ответ для каждой вершины , и прибавляем к нему , тем самым как бы приписывая в начало каждой из строк по одному символу.

Лексикографически k-ая подстрока

Условие . Дана строка . Поступают запросы — числа , и требуется находить -ую в порядке сортировки подстроку строки .

Асимптотика . на один запрос (где — это ответ на этот запрос, — размер алфавита).

Решение . Решение данной задачи базируется на той же идее, что и предыдущие две задачи. Лексикографически -ая подстрока — это лексикографический -ый путь в суффиксном автомате. Поэтому посчитав для каждого состояния количество путей из него, мы сможем легко искать -ый путь, двигаясь от корня автомата.

Наименьший циклический сдвиг

Условие . Дана строка . Требуется найти лексикографически наименьший её циклический сдвиг.

Асимптотика . .

Решение . Построим суффиксный автомат для строки . Тогда этот автомат будет содержать в себе как пути все циклические сдвиги строки .

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

Количество вхождений

Условие . Дан текст , и поступают запросы в виде: дана строка , требуется узнать, сколько раз строка входит в текст как подстрока (вхождения могут перекрываться).

Асимптотика . Препроцессинг и на один запрос.

Решение . Построим суффиксный автомат по тексту .

Дальше нам надо сделать такой препроцессинг: для каждого состояния автомата посчитать число , равное размеру множества . В самом деле, все строки, соответствующие одному и тому же состоянию, входят в одинаковое число раз, равное количеству позиций в множестве .

Однако явно поддерживать множества для всех состояний мы не можем, поэтому научимся считать только их размеры .

Для этого поступим следующим образом. Для каждого состояния, если оно не было получено путём клонирования (и начальное состояние мы также не учитываем), изначально присвоим . Затем будем идти по всем состояниям в порядке убывания их длины и пробрасывать текущее значение по суффиксной ссылке:

Утверждается, что в конце концов мы так посчитаем для каждого состояния правильные значения .

Почему это верно? Всего состояний, полученных не путём клонирования, ровно , и -ое из них появилось, когда мы добавили первые символов. Следовательно, каждому из этих состояний мы ставим в соответствие эту позицию, при обработке которой оно появилось. Поэтому изначально у каждого такого состояния , а у всех остальных состояний .

Оценка конкурентоспособности товаров осуществляется в следующей последовательности:

1) анализ рынка - изучение потребностей потенциальных покупателей и конкурентов;

2) формирование рыночных требований к товару и отражение их в структуре оценочных показателей;

3) выбор базы сравнения показателей;

4) выбор вида моделей оценочного класса;

5) оценка товаров по единичным и интегральным показателям конкурентоспособности;

6) вывод об уровне конкурентоспособности и решение о целесообразности его производства или приобретения;

Результатом изучения рынка с точки зрения оценки конкурентоспособности товара является сбор и систематизация информации о состоянии и динамике взаимодействия потребностей в товаре. Каждая потребность характеризуется набором определенных параметров, о содержании и величине которых покупатель заявляет на рынке в виде требований к товару.

Оценивать конкурентоспособность товаров можно, используя следующие методы и способы:

¨ Оценка конкурентоспособности с помощью товара – образца.

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

При определении набора подлежащих оценке и сравнению параметров конкурентоспособности товаров учитывают параметры, характеризующие потребительские свойства товара (потребительскую стоимость) и его экономические свойства (стоимость).

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

Для этого устанавливают иерархию параметров, выдвигая на первый план те, которые имеют наибольшую значимость («вес») для потребителя. Ранжирование показателей качества осуществляется каждым потребителем в процессе ответа на вопросы анкеты. Затем эти данные объединяются. Обладающие наибольшим «весом» параметры (приоритетные с точки зрения конкурентоспособности) в первую очередь становятся объектами тщательного исследования.

По аналогичной схеме определяется набор экономических (стоимостных) параметров товара, т.е. затраты покупателя на приобретение и использование изделия на протяжении всего периода его эксплуатации (потребления). В совокупности эти расходы составляют цену потребления - объем средств, нужных потребителю в течение всего срока службы товара.


Вначале рассчитывается сводный параметрический индекс, по которому дается оценка степени удовлетворения потребности покупателя в потребительских свойствах изделия.

После расчета параметрических индексов и «весов» каждого экономического параметра определяется сводный индекс конкурентоспособности по экономическим параметрам. На основе сводных индексов конкурентоспособности по потребительским и экономическим параметрам определяется интегральный показатель конкурентоспособности товара.

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

¨ Оценка конкурентоспособности товаров на базе суждений потребителей:

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

Для выяснения степени соответствия товара субъективным представлениям потребителей существует несколько способов.

Один из них - простые опросы потребителей о качестве товара. Для этого можно применить рейтинг шкалы типа "хорошо - плохо" или выстраивание продуктов в зависимости от их качества. В результате исследователи конкурентоспособности получают более близкую к действительности систему покупательских предпочтений.

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

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

Аj = ∑ Vi Iij (1),

где А - субъективная пригодность товара (отношение к товару);

Vi - важность мотива для потребителя;

Iij - субъективная оценка пригодности продуктаj для удовлетворения мотива i..

Использование этой модели связано с множеством проблем. Мотивы, важные для товара, часто бывают трудно определить. Высказывания опрашиваемых не дают указаний на то, какие характеристики продукта должны быть изменены.

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

Qj = ∑ Хk Yjk (2),

где Qj - оценка потребителями марки j ,

Хk - важность характеристики К (К = 1,..., n);

Yjk (-оценка характеристики К маркиj с точки зрения потребителей.

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

Qj = ∑ Wk {Bjk – Ik}r, (4),

где Qj - оценка потребителями марки j;

Wk - важность Bjk характеристики К (К = 1..., n);

Bjk - оценка характеристики К марки j с точки зрения потребителей;

Ik - идеальное значение характеристики К с точки зрения потребителей;

r - параметр, означающий при r =1 постоянную, а при r = 2 убывающую граничную пользу.

Таким образом, оценка конкурентоспособности товаров является комплексом исследований, включающих оценку качества товара, экономических, технических параметров. Кроме этого необходимо провести исследование товаров конкурентов, изучить потребности, запросы и требования потенциальных покупателей.

В результате оценку конкурентоспособности товара можно представить схематично (рис.4.15).

Оценка конкурентоспособности товара

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

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

Цели конкурентоспособности вытекают из целей и задач предприятия и маркетинга. Целями могут быть: завоевание доли рынка; лидерство на рынке по качеству товаров; сохранение доверия потребителей к товарам предприятия; поддержание достойной репутации на рынке. Могут быть и более конкретные цели, например, повышение объемов продаж определенного товара.

При определении показателей (параметров) товара подлежащих оценке, необходимо выбрать наиболее значимые, те, что ведут к достижению поставленной цели. Начинать нужно с нормативных параметров: патентная чистота, соответствие товара стандартам и нормам. Если товар не соответствует установленным нормативам, то дальнейший анализ конкурентоспособности нецелесообразен до принятия соответствующих мер по их обеспечению. Затем выделяют параметры товара для исследования по внешнему оформлению, технические параметры и экономические. Обычно это те свойства товара, которые в наибольшей степени удовлетворяют потребности покупателя. Поскольку главным оценщиком является потенциальный покупатель, все элементы конкурентоспособности товара должны быть ему понятны и очевидны, чтобы не возникали сомнения или иные толкования в отношении любого из них.

При выборе для сравнения товара-образца необходимо выполнить анализ: установленных целей оценки конкурентоспособности и выбора предполагаемых рынков сбыта; состояния рынка (объемов, продаж, факторов спроса и предложения); номенклатуры и установления величин показателей соответствующей потребности покупателей. Если нет возможности определить базу для сравнения, используют косвенный метод с помощью товара-образца (аналога). Товар-образец моделирует потребность и позволяет сравнить его параметры с товаром, подлежащим оценке. В этом случае конкурентоспособность оценивается путем сопоставления параметров реализуемых товаров с параметрами, необходимыми потребителю или с параметрами товара-образца. Сравнение производится по группам технических и экономических параметров.

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

При оценке конкурентоспособности товара применяют следующие методы: дифференциальный, комплексный или специальный. В результате проведения сравнения одним из методов дается конкретное заключение: продукция конкурентоспособна на данном рынке в сравниваемом классе товаров; продукция обладает низкой конкурентоспособностью в сравниваемом классе товаров на данном рынке; продукция полностью неконкурентоспособна в данном классе товаров на данном рынке.

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

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

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

Конкурентоспособность товара можно повысить путем изменения экономических, потребительских, технических и нормативных параметров; путем создания эффективной сбытовой сети и сервисного обслуживания; минимизации сроков доставки товаров от производителя к потребителю и др. Экономическими параметрами являются показатели полных затрат потребителя (цены потребления) по приобретению и использованию товара, определяемые его свойствами, а также условиями приобретения на конкретном рынке и использования. Технические и нормативные параметры представляют собой параметры назначения (классификационные, технической эффективности, конструктивные), эргономические параметры, параметры соответствия национальным стандартам, нормативам, законодательным актам и др. Одним из важных параметров товара считаются его эстетические свойства.

Основными условиями обеспечения конкурентоспособности товара являются: развитие рыночных отношений и предпринимательства, улучшение планирования, международная интеграция, действие механизма конкуренции и антимонопольного законодательства, направленность налоговой системы и кредитно-финансового механизма на рост конкурентоспособности; создание системы обеспечения конкурентоспособности объекта с ориентацией на интересы потребителя; обеспечение единства развития техники, технологии, управления, экономики; использование передовых методов исследований и разработок; рассмотрение в единстве качества (полезного эффекта) и совокупных затрат на продукцию.

Абсолютно конкурентоспособными являются новые виды товаров, не имеющие аналогов на рынке.

Из книги Теория организации: конспект лекций автора Тюрина Анна

10. Качество как фактор повышения конкурентоспособности Жесткая конкуренция в рыночной экономике заставляет производителей уделять большое внимание качеству производимого товара. Это его свойство, как правило, самое основное, на что прежде всего обращает внимание

Из книги Маркетинг автора Логинова Елена Юрьевна

30. Понятие товара, классификация товара Товар – это физические объекты, услуги, места, организации, идеи, рабочая сила или все то, что предназначено для обмена. Однако прежде чем включится в процесс обмена, он должен вызвать интерес у потенциального покупателя, т. е.

Из книги Маркетинг: конспект лекций автора Логинова Елена Юрьевна

33. Жизненный цикл товара. Разработка нового товара Типичный жизненный цикл товара состоит из нескольких стадий: разработка и внедрение; рост; зрелость; насыщение; упадок.После того как фирма разработала и создала свой товар, она выводит его на рынок. Принимает все

Из книги Маркетинг: Шпаргалка автора Автор неизвестен

2. Понятие товара, классификация товара Под товаром понимается все то, что может удовлетворить нужду или потребность и предполагается рынку с целью реализации.Товар– это физические объекты, услуги, лица, места, организации, идеи, рабочая сила или все то, что предназначено

Из книги Товарная политика предприятия автора Мельников Илья

11. Пути повышения конкурентоспособности товара Пути повышения конкурентоспособности товара выявляются в сравнении своего товара и фирмы с конкурентами. После проведения сравнения руководство принимает решение, по каким показателям следует обходить своих конкурентов,

Из книги Товарная информация автора Мельников Илья

Из книги Маркетинг для топ-менеджеров автора Липсиц Игорь Владимирович

Из книги Продвижение порталов и интернет-магазинов автора Гроховский Леонид О.

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

Из книги Бизнес-план на 100%. Стратегия и тактика эффективного бизнеса автора Абрамс Ронда

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

Из книги Невесомое богатство. Определите стоимость вашей компании в экономике нематериальных активов автора Тиссен Рене

Идея № 8 Что может стать основой вашей конкурентоспособности? Первейшая обязанность топ-менеджера - поиск способов обеспечения преимущества своей фирмы над конкурентами. В экономике административного типа это обеспечивается за счет «своих людей» в государственных

Из книги Стратегии развития научно-производственных предприятий аэрокосмического комплекса. Инновационный путь автора Баранов Вячеслав Викторович

Из книги МВА за 10 дней. Самое важное из программ ведущих бизнес-школ мира автора Силбигер Стивен

В начале этой главы приведем высказывание известного ученого в области управления качеством Э. Деминга: "Мы живем в эпоху ожидания всеобщего роста уровня жизни. Простая арифметика иногда помогает прочистить мозги. Откуда возьмутся земные блага, что обеспечат постоянно растущее предложение продуктов питания, одежды, жилья, транспорта и других услуг? Вряд ли возможен существенный экономический подъем, пока наша продукция не станет конкурентоспособной на внутреннем и внешнем рынках".

Оценка конкурентоспособности является исходным элементом для производственно-хозяйственной деятельности предприятий в условиях рыночной экономики. При этом систематической оценке должна подвергаться не только конкурентоспособность производимой предприятием продукции, но и конкурентоспособность самого предприятия.

Важность такой оценки обусловлена целым рядом обстоятельств, среди которых:

  • o необходимость разработки мероприятий по повышению конкурентоспособности продукции;
  • o выбор предприятием партнера для организации совместного выпуска продукции;
  • o привлечение средств инвестора для организации конкурентоспособного производства;
  • o составление маркетинговых программ для выхода предприятия на новые рынки сбыта;
  • o своевременное принятие решения об оптимальных изменениях товарного ассортимента, разработке и производстве новых и модернизированных изделий, расширении и создании производственных мощностей и др.

Оценка конкурентоспособности продукции может проводиться в соответствии с алгоритмом, приведенным на рис. 3.1.

На первом этапе должны быть определены цели анализа и оценки конкурентоспособности продукции. Оценка конкурентоспособности продукции может проводиться на различных стадиях жизненного цикла продукта (разработка, изготовление, продажа и эксплуатация), соответственно, цели оценки конкурентоспособности могут быть определены исходя из стадии жизненного цикла продукта.

Важнейший этап оценки конкурентоспособности продукции проведение маркетинговых исследований по изучению рынка, включающих изучение рыночного потенциала (емкости рынка), анализ рыночной сегментации, исследование фирменной структуры рынка и позиций конкурентов, изучение информации о покупателях.

На основании маркетинговых исследований формулируются требования к изделию. Основными критериями при этом выступают:

Рис. 3.1.

  • o технический уровень и уровень качества продукции;
  • o стандарты, документы законодательных органов страны-импортера и специфические требования потребителя;
  • o соответствие уровня качества продукции требованиям нормативно-технической документации;
  • o затраты потребителя на приобретение продукции, оплату таможенных сборов, налоги, транспортирование, монтаж, наладку, оплату запчастей, обслуживание и ремонт изделия, оплату материалов, топлива, энергии и т.п.

Сформулированные требования к изделию - это база для определения перечня параметров изделия, подлежащих оценке. Параметры количественно характеризуют свойства продукции. Следует отметить, что конкурентоспособность определяется только теми свойствами, которые представляют интерес для конкретного потребителя, поэтому все параметры изделия, выходящие за рамки этих свойств, не должны рассматриваться при оценке конкурентоспособности как не имеющие к ней отношения. Такое превышение параметров, с точки зрения потребителя, представляется бесполезным и даже может снизить конкурентоспособность товара в случае, если превышение параметров, характеризующих технический уровень продукции, будет способствовать повышению цены.

При определении перечня параметров изделия, подлежащих оценке, анализе нормативных параметров целесообразно руководствоваться:

  • o действующими международными (ИСО, МЭК и др.) и региональными стандартами;
  • o национальными отечественными и зарубежными стандартами;
  • o действующим законодательством, нормативными актами, техническими регламентами страны-экспортера и страны-импортера, устанавливающими требования к ввозимой в страну продукции;
  • o документацией на поставку;
  • o каталогами, проспектами и стандартами фирм - изготовителей данной продукции;
  • o патентной и конъюнктурно-экономической документацией и т.п.

Значительная роль в оценке конкурентоспособности продукции должна отводиться анализу нормативных параметров и условий конкурентоспособности продукции, классификация которых приведена на рис. 3.2. Первым шагом на этом этапе является оценка патентной чистоты продукции, отражающая степень воплощения в изделии технических решений, не подпадающих под действие патентов, введенных в стране, на рынке которой запланирован сбыт. Если в продукции имеются составные части, не обладающие патентной чистотой, то дальнейший анализ конкурентоспособности целесообразно проводить только после разработки и оценки мероприятий, направленных на обеспечение такой патентной чистоты.

При анализе нормативных параметров и условий следует определить принципиальные возможности продаж товара на конкретном рынке с точки зрения наличия нетарифных ограничений в торговле.

Рис. 3.2.

В процессе анализа внешнеторговой политики стран предполагаемого сбыта товара следует установить наличие прямых запретов (эмбарго) на его импорт, ограничение импорта (квотирование), а также выявить необходимость и принципиальную возможность получения лицензий на поставку планируемого количества товара (лицензирование).

Наряду с количественными ограничениями в торговле со страной предполагаемого импорта рассматриваются технические ограничения, к которым относятся технические регламенты и стандарты.

Технический регламент - документ, содержащий обязательные правовые нормы, утвержденный органом власти и устанавливающий обязательные для применения и исполнения требования к объектам технического регулирования (продукции, процессам производства и т.д.).

Соответствие продукции требованиям национальных технических регламентов - необходимое условие, обеспечивающее доступ продукции на внутренний рынок страны. Технические регламенты могут распространяться не на одну, а на несколько стран, т.е. рассматриваться как региональные технические регламенты.

Стандарты в большинстве стран мира - это нормативные документы, разработанные заинтересованными в этих документах сторонами (международные, региональные, национальные организации по стандартизации, производители, потребители, торговая сеть и т.п.).

Обычно в качестве необходимого условия допуска товара на внутренний рынок требуется подтверждение соответствия этого товара (услуги) техническим регламентам по безопасности жизни, здоровья и имущества граждан и окружающей среды, т.е. проведение обязательной сертификации товаров. Во многих странах приняты законы, охраняющие интересы потребителей и предусматривающие соответствующие санкции за их нарушение. Например, в странах ЕС с 1 января 1993 г. введены единые нормы и требования по безопасности потребительских товаров, продаваемых на рынке ЕС. Следует отметить, что согласно этой Директиве изготовитель должен информировать покупателя обо всех возможных рисках, связанных с потреблением его изделий, в инструкциях, при маркировке, на этикетке. В дополнение в феврале 1993 г. в ЕС принят специальный документ о контроле соответствия товаров, ввозимых из третьих стран (не стран ЕС), правилам безопасности. На его основе установлена специальная проверка импорта таких товаров, осуществляемая на внешних границах ЕС таможенными органами.

Большое значение для экспортеров имеет соблюдение экологических норм, предъявляемых к импортным товарам и странах-экспортерах. Так, например, в большинстве стран Западной Европы обязательным стало оснащение автомобилей специальным оборудованием для очистки выхлопных газов, и был запрещен импорт автомобилей без этого оборудования. Ряд западноевропейских стран при ввозе сельскохозяйственной продукции требуют сертификаты на соответствие допустимым нормам радиоактивности.

В качестве ограничения на ввоз товаров в страну экспорта может выступать несоответствие процедур сертификации в стране-экспортере и стране-импортере. Средством устранения такого рода препятствий является гармонизация национальных систем сертификации путем заключения соглашений.

По отдельным товарам ограничением при их экспорте может стать требование покупателя о соответствии системы менеджмента качества предприятия-изготовителя международным стандартам ИСО серий 9000, 14000 и др. (подробно этот вопрос будет рассмотрен в гл. 6).

Барьером на пути экспорта могут стать и различные обязательные требования к маркировке и этикетированию товаров. Так, в некоторых странах обязательно наличие надписи на упаковке на двух официальных языках, принятых в стране. Например, в Швеции на упаковке продовольственных и аптекарских товаров необходимо указывать содержимое на шведском и финском языках, а в Канаде и, английском и французском.

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

Методически учет нормативных параметров при оценке конкурентоспособности обеспечивается путем введения специального показателя, который может принимать лишь два значения: 1 или 0. Если изделие соответствует нормативным параметрам и условиям, то показатель равен 1, если нет - 0. Групповой показатель по всем нормативным параметрам представляет собой произведение единичных показателей:

где 1Х - групповой показатель по нормативным параметрам; т - число нормативных параметров; 0,^ - единичный показатель по £-му нормативному параметру.

Следующий этап оценки конкурентоспособности продукции - формирование группы аналогов. Все включаемые в группу аналогов изделия должны отвечать следующим критериям:

  • o конкурирующая и оцениваемая продукция должны быть аналогичны по назначению и условиям эксплуатации и ориентированы на одну группу потребителей;
  • o изделие-конкурент должно отвечать цели оценки конкурентоспособности;
  • o представительность изделия-конкурента на рынке в момент оценки и тенденции ее изменения на перспективу должны подтверждаться достоверной информацией.

И группу аналогов при оценке разрабатываемой продукции могут входить перспективные образцы, поступление которых па мировой рынок прогнозируется на период выпуска оцениваемой продукции, или идеальная потребительская модель, удовлетворяющая перспективные потребности определенного сегмента рынка на 100%. При оценке выпускаемой продукции в группу аналогов могут быть включены образцы, реализуемые на мировом рынке, либо использована идеальная потребительская модель.

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

  • 1) аналог не может быть признан базовым образцом и исключается из последующих сопоставлений, если он уступает другому аналогу но совокупности оценочных показателей, т.е. уступает другому аналогу хотя бы по одному показателю, не превосходя его ни по каким другим;
  • 2) оба аналога остаются для дальнейшего сопоставления с другими, если по одним показателям оказывается лучше первый аналог, а по другим - второй, при этом значения некоторых показателей у аналогов могут совпадать.

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

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

Кроме того, при оценке конкурентоспособности продукции следует также принимать во внимание конкуренцию сопутствующих товаров и услуг и прогнозировать ее возможное влияние на конкурентоспособность оцениваемой продукции.

Следующий этап оценки конкурентоспособности продукции - анализ уровня качества, цены потребления, организационно-коммерческих показателей.

Анализ уровня качества проводится на основе квалиметрической оценки (см. гл. 2).

Цена потребления характеризует полные затраты покупателя на приобретение и эксплуатацию (или потребление) изделия и, соответственно, рассчитывается на основе экономических показателей, характеризующих цену продажи товара и эксплуатационные расходы на весь срок службы изделия (или потребление изделия). Цена потребления изделия может быть рассчитана по формуле

где Рс - цена потребления изделия; Рг/ - цена продажи изделия; Оек1 - эксплуатационные расходы на /"-й год службы;

г - коэффициент приведения к современной стоимости; г - норма дисконта; С - срок службы изделия; / - год приведения.

При анализе качества и цены потребления изделия проводится расчет параметрических индексов дифференциальным, комплексным и смешанным методами оценки (подробно рассмотрены в параграфе 2.3).

Интегральный показатель конкурентоспособности продукции определяется как соотношение суммарного полезного эффекта, рассчитанного как комплексный показатель по параметрам качества, и полных затрат на приобретение и использование товара (цены потребления), рассчитанных как комплексный показатель по экономическим параметрам:

где Сы - интегральный показатель конкурентоспособности товара; () - сводный параметрический индекс по показателям качества товара; Рс. - сводный параметрический индекс по цене потребления товара.

При С1п1 > 1 продукция конкурентоспособна на конкретном рынке, при Сш < 1 продукция неконкурентоспособна на конкретном рынке.

На этапе анализа уровня качества и цены потребления изделия важны выбор используемых при оценке конкурентоспособности продукции параметров и определение величины их весовых коэффициентов. Чаще всего при этом используются экспертные оценки, однако они содержат значительную долю субъективизма и требуют высокой квалификации экспертов, участвующих в оценке.

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

  • o математическое ожидание для параметра будет соответствовать оптимальному значению этого параметра для данной группы изделий;
  • o величина среднеквадратичного отклонения параметра покажет значимость этого параметра для оценки конкурентоспособности; чем больше среднеквадратичное отклонение, тем менее значительно влияет данный параметр на конкурентоспособность и тем меньше весовой коэффициент для данного параметра;
  • o возможно использование математических ожиданий всех параметров как набор базовых величин для оценки конкурентоспособности дайной группы изделий;
  • o анализируя изменение математического ожидания по каждому параметру за некоторый период времени, можно спрогнозировать ожидаемую величину этого параметра в будущем; таким образом проводится анализ конкурентоспособности для проектируемых изделий.

При оценке конкурентоспособности продукции также должны приниматься во внимание организационно-коммерческие показатели, отражающие условия (реальные или потенциальные) продажи этой продукции. Методически в оценке конкурентоспособности продукции эти показатели могут быть оценены путем экспертных оценок или статистических методов.

На основе проведенного расчета интегрального показателя конкурентоспособности и анализа организационно-коммерческих показателей делается вывод о конкурентоспособности изделия по сравнению с базовыми образцами и формируется политика предприятия в отношении оцениваемого изделия. В случае положительного исхода оценки (показатели оцениваемого изделия превышают показатели базовых образцов) предприятие принимает решение в соответствии с поставленными целями анализа и оценки конкурентоспособности продукции - о проектировании, разработке, производстве, выходе на рынок и т.п. В случае отрицательной оценки происходит выработка технико-экономических решений по повышению конкурентоспособности продукции.