Все выпуски

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

The route problem with precedence conditions and cost functions depending on the jobs list is considered; these singularities correspond to engineering applications. In particular, the above-mentioned singularities exist in statements of some problems arising in nuclear energetics and in machines with numerical control. Problems involved in sequentially circuiting megalopolises and in carrying out some (interior) work during these circuits are investigated. A procedure for local improvement of heuristic solutions for problems of perceptible dimension is proposed; this procedure exploits insertions on the dynamic programming base. Dynamic programming is realized in the form of a variant that does not provide for construction of a “full” array of values of the Bellman function. The search for localization of an insertion involves restricting to the variant of the Bellman procedure that realizes the extremum of the (local) criterion without constructing a corresponding solution in the form of a route-track pair. A more complete and more cost-intensive (in the sense of memory resources) procedure including determination of the above-mentioned (local optimal) solution is planned after the choice of the insertion localization.

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

The problem of proximity full-text search is considered. If a search query contains high-frequently occurring words, then multi-component key indexes deliver improvement of the search speed in comparison with ordinary inverted indexes. It was shown that we can increase the search speed up to 130 times in cases when queries consist of high-frequently occurring words. In this paper, we are investigating how the multi-component key indexes architecture affects the quality of the search. We consider several well-known methods of relevance ranking; these methods are of different authors. Using these methods we perform the search in the ordinary inverted index and then in the index that is enhanced with multi-component key indexes. The results show that with multi-component key indexes we obtain search results that are very near in terms of relevance ranking to the search results that are obtained by means of ordinary inverted indexes.

Рассматривается задача полнотекстового поиска с учетом близости в больших текстовых массивах. Пользователь вводит несколько слов в качестве поискового запроса. В результате поиска формируется список документов, содержащих заданные слова. В современных поисковых системах, документы, в которых слова поискового запроса встречаются вблизи, считаются более релевантными. Рассматриваемая задача требует сохранения в индексе информации о каждом вхождении каждого слова в индексируемых текстах. Скорость выполнения поискового запроса зависит от числа вхождений слов запроса в текстах. Следовательно, запросы, включающие часто встречающиеся слова, выполняются существенно медленнее, чем запросы, состоящие из обычных слов. Для каждого слова текста сохраняем в индексах информацию о часто встречающихся словах, которые располагаются в тексте рядом с ним, на расстоянии не более $MaxDistance$. Данный параметр может принимать значения 5, 7 и даже больше. Применение индексов с трехкомпонентными ключами позволяет добиться быстрого выполнения поисковых запросов. Результаты экспериментов поиска, представленные автором ранее, показывают, что среднее время поискового запроса, состоящего из очень часто встречающихся слов, при применении индексов с трехкомпонентными ключами, меньше в 94.7 раза, чем среднее время поиска с использованием обычных инвертированных индексов. В текущей работе рассмотрен новый алгоритм создания индекса с трехкомпонентными ключами. Доказана корректность алгоритма. Представлены результаты экспериментов построения индексов для разных значений параметра $MaxDistance$.

Proximity full-text searches in large text arrays are considered. A search query consists of several words. The search result is a list of documents containing these words. In a modern search system, documents that contain search query words that are near each other are more relevant than other documents. To solve this task, for each word in each indexed document, we need to store a record in the index. In this case, the query search time is proportional to the number of occurrences of the queried words in the indexed documents. Consequently, it is common for search systems to evaluate queries that contain frequently occurring words much more slowly than queries that contain less frequently occurring, ordinary words. For each word in the text, we use additional indexes to store information about nearby words at distances from the given word of less than or equal to $MaxDistance$, which is a parameter. This parameter can take a value of 5, 7, or even more. Three-component key indexes can be created for faster query execution. Previously, we presented the results of experiments showing that, when queries contain very frequently occurring words, the average time of the query execution with three-component key indexes is 94.7 times less than that required when using ordinary inverted indexes. In the current work, we describe a new three-component key index building algorithm. We prove the correctness of the algorithm. We present the results of experiments of the index creation depending on the value of $MaxDistance$.