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

«Что будет если Пиноккио скажет „У меня сейчас увеличится нос“?» — эту фразу пару дней назад озвучил один мой знакомый. При этом мы находились в кругу наших товарищей и между нами сразу разразился спор. Кто-то говорил, что нос вырастет, кто-то, что нос останется прежним и ничего не произойдет, а кто-то вообще, что образуется черная материя и произойдет взрыв. Естественно последний вариант был шуткой и его ни кто не воспринял его в серьез. И так, мы разделились на две части. Первая половина приводила различные аргументы, которые может в чем-то и были верны, но тут же опровергались второй половиной. В начале я тоже участвовал в этой дискуссии, но потом понял, что этим спором мы ни чего не решим и решил рассмотреть этот вопрос с точки зрения программирования. В тот момент я находился не дома и поэтому вместо того, что бы сесть на компьютер, я взял листок бумаги и начал думать. Первое, что пришло в голову это то, что нужно всё-таки разобраться, а как же работает нос Пиноккио? Я взял ручку и начал посторочно выписывать действия, которые происходят с носом. Начиная первым и заканчивая последним пунктом.

1. Вместо вступления.

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

Собственно, главное отличие алгоритма от, например, «наивного сравнения», заключается в том, что в его основе лежит логические операции, а именно логическое умножение (оно же AND, оно же конъюнкция).

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