Компьютерный текстовый документ как структура данных

Обновлено: 03.07.2024

Мне нужно отсортировать эти записи по последнему числу с помощью алгоритма сортировки вставками, поэтому вторая запись должна быть первой в списке, поскольку 2>1. Для этого мне сначала нужно сохранить каждую запись перед их сравнением, у меня с этим проблемы.

У меня есть это до сих пор:

Мои текущие проблемы:

1) эта текущая программа не подходит для сохранения строки слов. Хорошо, когда запись такая: string; нить; нить; 1, но не работает с фразами (как в первом примере).

2) Я не очень понимаю структуру этого: я знаю, что сохраняю каждую запись в своем массиве структур данных, но у меня возникают проблемы с печатью каждой записи. Допустим, я хочу напечатать вторую запись, как я могу это сделать? В моей текущей работе я напечатал один, два, три и st, но таким образом будет напечатана только первая запись.

3 ответа 3

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

Вместо этого лучшим решением было бы прочитать всю строку в строку и проанализировать ее. Следующий фрагмент кода считывает строку текста с помощью fgets, а затем использует strtok, чтобы разбить ее на фрагменты, разделенные точкой с запятой. Он отслеживает, какое поле он заполняет, используя field_number, поэтому, если вы добавите больше полей, его легко расширить. И если полей меньше, чем ожидалось, он остановится и перейдет на следующую строку.

Отвечая на ваш второй вопрос, elements — это массив. Если вы делаете elements->one, это то же самое, что и elements[0].one . Если вы хотите получить доступ ко второму элементу в вашем массиве, вы должны сделать elements[1].one или (elements+1)->one, что вы и делаете с этой странной строкой в исходном коде:

когда на самом деле вам следовало бы использовать elements[i], так как это намного легче читать.

Текстовый редактор — это программа, которая позволяет пользователю открывать, просматривать и редактировать текстовые файлы (файлы, содержащие только текст). Они важны для современного мира, так как многие люди часто пытаются открыть текстовый файл и просмотреть его содержимое. Большинство из нас раньше взаимодействовали или слышали о текстовых редакторах, таких как Atom, Vim, Visual Studio Code и так далее. Текстовые редакторы со временем развивались, становились быстрее и предоставляли больше возможностей, чем их конкуренты.

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

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

Vert Important Не существует четкого решения, поскольку все текстовые редакторы различаются используемыми структурами данных. Текстовые редакторы в прошлом или те, которые используются в настоящее время, использовали эти структуры данных, перечисленные ниже.

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

Char Buffer (Array) / String тип данных

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

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

Гэп-буфер

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

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

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

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

Модель с двумя стеками

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

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

Двойной связанный список

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

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

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

Всегда существует подход массивов массивов, но он уступает подходу двусвязного списка.

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

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

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

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

B-дерево / B+ дерево

И B-дерево, и B+ дерево отличаются друг от друга, но дают несколько схожие результаты, поэтому они сгруппированы вместе. Эти деревья можно использовать по-разному, например, используя другие структуры данных в узлах, сохраняя при этом хорошую производительность доступа, они полезны для разделения разделов текста и других применений, которые люди могут разумно придумать.

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

Преимущества Хорошая производительность доступа и редактирования может быть потенциально хорошей в зависимости от того, как вы используете дерево.
Недостатки Большой объем памяти, более высокая сложность реализации, и может быть непонятно, как правильно использовать эту структуру данных.

Таблица деталей

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

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

Другие почетные упоминания

Вот другие структуры данных, которые следует учитывать:

Застежка-молния / пальчиковые деревья

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

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

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

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

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

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

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

Набор ссылок, посвященных различным аспектам текстового редактора, от проектирования до реализации.

Почти всем им не хватает функциональности.

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

Изображения

Итан З. Букер

Разработчик программного обеспечения, стажер в OpenGenus | Студент Висконсинского университета в Ла-Кроссе

Улучшено и проверено:

< бр />

Уэ Киао, доктор философии

Фонд OpenGenus

Структуры данных

Модель с двумя стеками / разделенный буфер для текстовых редакторов

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

Обратить двусвязный список в C++

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

Харини Джеяраман

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

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

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

Банда четырех шаблонов проектирования использует обработку текста для значительного числа своих примеров. Эти примеры могут оказаться полезными для решения различных проблем в разработке текстовых процессоров.

@MichaelT: это действительно так, это была и моя первая мысль. Я не смог найти в нем примеров, связанных с этим конкретным вопросом, хотя мне следует взглянуть еще раз.

@MichaelT: да, это были главы, которые я просмотрел. В частности, они касаются того, как хранить элементы документа в виде объектов и как проектировать свои API, чтобы они могли отображать себя. В нем не обсуждается, как сопоставить позицию курсора пользователя/выделенный текст с представлением документа.

4 ответа 4

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

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

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

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

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

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

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

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

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

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

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

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

Представьте, что все отформатированное представление вашего документа похоже на высокое растровое изображение. То, что пользователь видит на экране, представляет собой прямоугольную часть этого растрового изображения, выбранную на основе положения прокрутки и настроек масштабирования, так что это всего лишь небольшая арифметика для преобразования положения мыши x, y в координату (u, v) в нашем «растровом изображении». пространство."

Наша структура пространственного подразделения может быть деревом вложенных прямоугольников, которые делят пространство растрового изображения с конечными узлами, которые ссылаются на позиции в пространстве документа. Это позволило бы нам запросить координату (u, v), чтобы получить местоположение документа за время O(log n).

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

Мы можем сократить объем бухгалтерского учета, необходимого для этих волновых эффектов, используя относительные родительские координаты для прямоугольников и позиций документа в нашем дереве подразделений. Редактирование, которое добавляет или удаляет конечный узел, влияет (в лучшем случае) только на размеры его предков и смещения его младших братьев и сестер. Это O(log(n) + m), где n — длина документа, а m — количество младших братьев и сестер.

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

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

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

Приложения

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

Прямой подход

Самый простой подход – циклически перебирать поисковые фразы и искать в тексте каждую фразу одну за другой. Этот подход плохо масштабируется. Поиск строки внутри другой имеет сложность O(n) . Повторение этого для m поисковых фраз приводит к ужасному O(m * n) .

Запустив этот код на моем компьютере для разработки [1] на тестовом образце [2], я получил время выполнения 1 час 14 минут — намного больше времени, которое вам нужно, чтобы взять чашку кофе, встать и потянуться или любой другой предлог, который разработчики используют, чтобы пропустить работу.

Лучший подход – попытка

Предыдущий сценарий можно улучшить несколькими способами. Например, процесс поиска можно разделить и распараллелить на нескольких процессорах/ядрах. Но сокращение времени выполнения, достигнутое при таком подходе (общее время выполнения 20 минут при идеальном разделении на 4 процессора/ядра), не оправдывает дополнительной сложности кодирования/отладки.

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

Структура данных, которая особенно хорошо подходит именно для этого сценария, — это trie. Эта универсальная структура данных обычно упускается из виду и не так известна, как другие древовидные структуры, когда дело доходит до задач поиска.

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

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

Преимущество троицы в том, что она значительно сокращает время поиска. Чтобы упростить понимание этого руководства по трем, давайте представим бинарное дерево.Обход бинарного дерева имеет сложность O(log 2 n) , поскольку каждый узел разветвляется на два, сокращая оставшийся обход вдвое. Таким образом, тройное дерево имеет сложность обхода O(log 3 n) . Однако в дереве число дочерних узлов определяется последовательностью, которую оно представляет, а в случае читаемого/осмысленного текста количество дочерних узлов обычно велико.

Алгоритм текстового поиска

В качестве простого примера возьмем следующие поисковые фразы:

«одна семья»
"другая семья"
«отдельное существование»
«члены лиги»

Помните, что мы заранее знаем наши поисковые фразы. Итак, начнем с создания индекса в виде дерева:

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

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

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

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

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

Давайте применим этот алгоритм к нашему примеру структуры данных trie и посмотрим, что получится:

Шаг	Индикатор Trie	Индикатор текста	Match?px">are	-	Переместить в начало	Перейти к следующему
4	start	members	members	Перейти к членам	Перейти к следующему
5	members	of	of	Перейти к	Перейти к следующему
6	of			Перейдите к	Перейти к следующему
7		такой же	-	Переместить в начало	-
8	start	такой же	такой же	Перейти к тому же	Перейти к следующему
9	такой же	family	family	Переместить в начало	Перейти к следующему
10	start	их	-	Переместить в начало	Перейти к следующему
11	start	separate	separate	Переместить, чтобы отделить	Перейти к следующему
12	separate	existence	existence	Переместить в начало	Перейти к следующему
13	start	is	-	Переместить в начало	Перейти к следующему
14	start	a	-	Переместить в начало	Перейти к следующему
15	start	myth	-	Переместить в начало	Перейти к следующему

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

Реальный пример

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

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

Индексирование

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

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

Поиск

Процесс поиска является прямой реализацией алгоритма дерева, описанного в руководстве выше:

Производительность

Представленный здесь код взят из реального проекта и упрощен для целей данного документа. Повторный запуск этого кода на той же машине [1] и с тем же тестовым образцом [2] привел к тому, что время выполнения составило 2,5 секунды для построения дерева и 0,3 секунды для поиска. Так много для перерыва, а?

Варианты

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

Например, если начало одного поискового запроса совпадает с некоторой частью другого поискового запроса, например:

«поделиться и наслаждаться с друзьями»
"У меня есть два билета, которыми я хочу поделиться с кем-то"

и текст содержит фразу, из-за которой указатель trie начинает двигаться по неверному пути, например:

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

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

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

Заключение

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

Как видно из приведенного выше руководства по структуре данных trie, очень важно тщательно выбрать правильный алгоритм для решения поставленной задачи. В данном конкретном случае подход trie сократил время выполнения на ошеломляющие 99,93 %, с более чем часа до менее чем 3 секунд.

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

[1] Машина, используемая для этого теста, имеет следующие характеристики:

[2] Тестовая выборка состоит из 280 тысяч поисковых фраз общим размером 23,5 МБ и основного текста размером 1,5 МБ.

Вы можете использовать данные электронной таблицы, хранящиеся в текстовом файле со значениями, разделенными запятыми (CSV) (.csv), или данные, хранящиеся в текстовом файле с разделителями (.txt) или в файле формата GPS Exchange Format (.gpx) в ArcGIS Online. В следующем списке приведены сведения о том, как можно использовать эти файлы, и приведены ссылки на инструкции. Разделы после списка функций содержат информацию о правильном форматировании и советы по использованию файлов CSV, TXT и GPX в вашей организации ArcGIS Online.

В настоящее время эта функция поддерживается только в Map Viewer Classic. Он будет доступен в будущих версиях Map Viewer .

Файлы CSV и TXT

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

Поскольку в файле не применяются принудительные типы данных, ArcGIS Online полагается на имена полей и особое форматирование в полях для интерпретации типа данных, который следует применить.

Поля местоположения в файлах CSV и TXT

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

долгота, широта*
широта, долгота*
Военная сетевая справочная система (MGRS)
Национальная сеть США (USNG)

Если Map Viewer Classic не может определить информацию о координатах или вместо этого ваш файл содержит информацию об адресе или месте, вам будет предложено просмотреть поля местоположения и при необходимости изменить их.

Поддерживаются следующие поля местоположения:

Широта, долгота
Широта, долгота
Долгота83, Широта83
Лонгдекдег, Латдекдег
Лонг_дд, Латдд
Длина
Y, X
Центр Y, Центр X
Центр X, Центр Y
Точка-y, точка-x
Точка-x, точка-y
МИГР
USNG
Адрес
Город
Штат
Архив

Дата и время в файлах CSV

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

Всякий раз, когда отображается поле даты, дата преобразуется из времени UTC в ваше местное время. Это делается путем запроса вашего компьютера и запроса его настройки часового пояса. Например, предположим, что на вашем компьютере установлено тихоокеанское время (США и Канада). Тихоокеанское время отстает от UTC на восемь часов, за исключением перехода на летнее время: когда время UTC равно 10:00, это 2:00 по тихоокеанскому времени.

При публикации размещенного векторного слоя из CSV-файла вы можете указать часовой пояс данных. Указанный часовой пояс используется для уменьшения смещения, поскольку ArcGIS Online предполагает, что данные о дате и времени указаны в формате UTC. Например, если CSV-файл, содержащий поля даты, публикуется с тихоокеанским временем, выбранным в качестве часового пояса, ко всем значениям даты и времени в вашем CSV-файле будет добавлено восемь или семь часов как часть преобразования в UTC, в зависимости от того, является ли дата значения попадают в летнее время.

Если поля даты в вашем CSV-файле содержат дату, но не значение времени, при публикации размещенного векторного слоя назначается значение времени в полночь. Поэтому, если вы не укажете часовой пояс при публикации, ваши данные будут храниться со значением времени в полночь (UTC). Когда вы просматриваете данные, время будет преобразовано в местное время, что может привести к изменению даты. Например, 28.07.2009 0:00 — это полночь (UTC) 28 июля 2009 года. Если вы просматриваете данные с компьютера в тихоокеанском часовом поясе, дата и время будут отображаться как 27.07.2009 17 :00. Указание часового пояса при публикации устраняет это смещение при просмотре в указанном часовом поясе.

При публикации размещенного векторного слоя из файла CSV поддерживаются следующие даты:

Читайте также: