Канонизации алгоритмы

Одной и той же структурной формуле может соответствовать множество матриц как вида 1а, так и вида 16. Выбор одной из этих матриц осуществляется алгоритмом канонизации, описываемом нами в гл. V. [c.94]

Алгоритм канонизации Моргана [c.104]

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

В отличие от универсальных алгоритмов рассматриваемый специализированный алгоритм канонизации оперирует не с таблицей связей, а с входной линейной записью, что дает существенный выигрыш памяти и времени канонизации [75, 76]. В рамках специализированной ИПС для ароматических соединений этот алгоритм позволяет исключить из технологической схемы ИПС алгоритм перевода входной линейной записи в таблицу связи. [c.108]

Рассматриваемый алгоритм канонизации интересен как специализированный подход к канонизации химических графов, приводящий к существенному упрощению алгоритма. Хотя этот алгоритм реализован в рамках специализированной ИПС (для обширного класса циклических соединений с сопряженными связями), он может найти применение также в универсальной ИПС федеративного типа, в которой предусмотрены различные алгоритмы для различных больших классов соединений. Каноничные входные коды на языке ПНК могут быть переведены в каноничные поатомные матрицы связи. [c.108]

Характерной особенностью рассматриваемого алгоритма является то, что для некоторого класса циклических систем исключается многоступенчатая классификация вершин, что упрощает алгоритм. Принят фрагментарный принцип канонизации, т. е. канонизация собственно циклических систем и ациклических цепей проводится раздельно. В каноничном коде храпения автономия циклической и ациклической систем сохраняется. [c.108]

Выбор каноничного синонима. Код ПИК позволяет просто провести канонизацию регулярных структур в соответствии с правилами старшинства Паттерсона [23]. Поскольку выбор синонима в качестве каноничного безразличен, то задача точного следования правилам Паттерсона в рассматриваемом алгоритме не ставилась. Выбор каноничного синонима осуществляется по трем простым критериям min t , где — число слогов в синониме тах ta, где tj — число символов kt fE d , kt е К == 1, 2, 3, dl — первый слог синонима тах tg, где tg — числовое представление синонима. [c.113]

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

Объединяя понятия метакод и код хранения , можно было бы говорить об общем алгоритме канонизации, который переводит входные коды в коды хранения. Однако процедура машинной генерации метакода автономна относительно основной процедур . канонизации. Ири генерации метакодов достаточен анализ связей менаду вершинами графа и не требуется проведения набора процедур классификации отметок вершин и ребер химического графа, что характерно для алгоритма канонизации. Впрочем, это разграничение достаточно условно. [c.93]

Входом рассматриваемой системы канонизации является список вершин структуры, в котором описывается отметка (атомный символ) каждой вершины и ее ребра, т. е. связи с другими вершинами структуры. Эта мат-рица преобразуется вычислительной машиной в таблицу связи, разработанную Глюком в фирме Du Pont [27, 28]. Таблица составляется с учетом некоторых правил перечисления вершин, в частности, задается определенный порядок очередности записи вершин структуры. Хотя эта таблица и не является однозначной, но она удобна для дальнейшей работы алгоритма канонизации. [c.104]

Канонизация ациклических цепей. Выше уже говорилось, что в рассматриваемом алгоритме реализован принцип фрагментной канонизации и, в частности, записи циклической системы и заместителей канонизируются раздельно. В алгоритмах канонизации, в которых все вершины химического графа включаются в одну матрицу и индивидуальность заместителей практически отсутствует, нет особого смысла говорить о статистике ацик-.лических цепей в химических графах. Иначе обстоит дело нри фрагмент-ной канонизации. При этом уже ва/кен вопрос какие ациклические цепи встречаются чаш,е При таком подходе технологичность алгоритма канонизации четко определяется приспособленностью к обработке наиболее распространенных ациклических и циклических систем. Среди органических соединений встречаются соединения, содержаш ие разветвленные ациклические цени. Число возможных путей в подобных сложных ациклических ценях может достигнуть нескольких сотен. Одпако такие цепи встречаются намного реже, чем простые цепи. Было бы тактически неверно ослон нять обработку простых распространенных ациклических цепей, приспосабливая алгоритм к общему, но редко встречающемуся случаю сильно разветвленной ациклической цепи. В системе ПНК, как и в системе Висвессера, используется краткое обозначение некоторых разветвленных грунн (— СО —, [c.113]

После конечного символа записи ациклической цепи в коде ПНК ставится вершина циклической системы, к которой подходит заместитель, т. е. буква из ряда т, у, ф, х, ц, ч . В рассматриваемом примере этим последним символом является символ у. Алгоритм строит различные стволы, т. е. пути от концевого атома к конечному символу (например, Э] ). Один ствол записан кодировщиком — это цепочка символов, находящаяся вне скобок (в примере цепочка аца1оа9а4аза2а1). Строить все стволы необязательно, так как некоторые стволы можно отсекать в соответствии с правилами старшинства на начальных этапах. Например, при правиле выбора в качестве каноничного ствола, содержащего наибольшее число символов, нет необходимости строить стволы от концевых атомов а , а и Эз, так как ветви в скобках (а Эд, и а ) содерншт соответственно 2, 1 и 1 символ, в то время как часть ствола перед символом ветвления 84, т. е. ац а ад, содержит три символа. Определение ветви сравнительно простое ветвь — это цепочка, располон<енная между парой символов (и , или и , или и), причем сами указанные символы не могут входить в состав цепочки. Выше рассматривалась скобка первого порядка. Аналогичный подход применяется и в сложных случаях скобок в скобке . Если часть кода внутри скобки п-го порядка рассматривается в качестве обобщенной вершины, алгоритм сводит сложный ациклический граф к графу с обобщенной скобкой первого порядка. В этом случае время автоматической канонизации возрастает, но очень сложные ациклические цепи встречаются редко. Выбор каноничного синонима ациклической цепи проводится по простым критериям старшинства Ь - — число отметок вершин в стволе ациклического графа — числовое представление ствола графа — числовое представление всего кода ациклического графа. Как правило, для наиболее распространенных ациклических цепей достаточно сравнение по 1-му и [c.114]

Алгоритм канонизации слов, реализованный па ЭВМ БЭСМ-4, содержит 11648 команд. Машинный эксперимент по канонизации ароматических, частично насыщенных и гетероциклических структур с различными заместителями, показал, что среднее время канонизации одной структуры равно 1,2 сек. [c.115]

Перевод каноничного ПНК-кода в каноничную поатомную матрицу связи произвольного типа. В настоящее время известны десятки тысяч сложных полициклических соедипений, относящихся к рассматриваемому классу регулярных систем (красители, полупродукты и т. д.). Канонизация подобных систем с помощью поатомной матрицы связи может потребовать больших затрат машинного времени. Как известно, пе имеет значения, какой синоним из множества синонимов выбран в качестве каноничного, поскольку основное требование при канонизации заключается лишь в том, чтобы для данной структуры в качестве каноничного всегда выбирался один и тот же синоним. Отсюда можпо сделать вывод, что вовсе не обязательно, чтобы записи всех структур приводились к каноничному виду на основе общих правил лексиграфического старшинства. Вполне возможно разбить множество структурных формул па классы и внутри данного класса использовать свои п )авила старшинства, т.е. фактически свою процедуру канонизации. Описанный специализированный алгоритм канонизации может быть применен в универсальной ИПС, использующей поатомные матрицы связи согласно следующей схеме. [c.115]

В алгоритмическом отношении основу машинного поиска семейств родственных соединений составляет поиск соединений, содер5кащих заданный фрагмент. При этом задача идентификации структур (поиска заданной структуры) является частным предельным случаем поиска но фрагментам, когда фрагмент эквивалентен самой структуре. Поиск химических рядов в соответствии с моделью, предложенной в гл. VII, в общем тоже может быть вынолнен с помощью некоторой модификации обычного алгоритма поиска по фрагментад . В информационных системах с каноничным языком храпения идентификация структур принципиально отличается от поиска по фрагментам и сводится к простой проверке кодов на совпадение. Эта процедура элементарна, и поэтому в подобных системах задача идентификации решается алгоритмом канонизации. [c.147]

Описываемый алгоритм был разработан для специализированной ИПС, охватываюш,ей циклические соединения с сопряженными связями. В этом алгоритме используются в основном те же блоки, что и в алгоритме канонизации кодов ПНК, рассмотренном в гл. 5. Основная идея алгоритма заключается в том, что с помощью некоторого оператора Р генерируется [c.159]

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

Справочник химика 21

Химия и химическая технология