Algorithm for word segmentation based on the shortest path algorithm inside a graph
The features of word segmentation algorithms from such texts are considered. There are two main models, namely, statistical one and the one using a dictionary. For models with a dictionary, a variant of the maximal matching algorithm is noted for which there are modifications such as Forward Maximal...
Збережено в:
| Дата: | 2017 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | rus |
| Опубліковано: |
Інститут проблем реєстрації інформації НАН України
2017
|
| Теми: | |
| Онлайн доступ: | http://drsp.ipri.kiev.ua/article/view/142917 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Data Recording, Storage & Processing |
Репозитарії
Data Recording, Storage & Processing| id |
drspiprikievua-article-142917 |
|---|---|
| record_format |
ojs |
| institution |
Data Recording, Storage & Processing |
| collection |
OJS |
| language |
rus |
| topic |
words segmentation word segmentation quality web resources monitoring shortest path search wave algorithm сегментация слов сегментатор качество сегментации слов мониторинг поиск кратчайшего пути волновой алгоритм сегментація слів сегментатор якість сегментації слів моніторинг пошук найкоротшого шляху хвильовий алгоритм |
| spellingShingle |
words segmentation word segmentation quality web resources monitoring shortest path search wave algorithm сегментация слов сегментатор качество сегментации слов мониторинг поиск кратчайшего пути волновой алгоритм сегментація слів сегментатор якість сегментації слів моніторинг пошук найкоротшого шляху хвильовий алгоритм Lande, D. V. Berezin, B. A. Pavlenko, O. Yu. Algorithm for word segmentation based on the shortest path algorithm inside a graph |
| topic_facet |
words segmentation word segmentation quality web resources monitoring shortest path search wave algorithm сегментация слов сегментатор качество сегментации слов мониторинг поиск кратчайшего пути волновой алгоритм сегментація слів сегментатор якість сегментації слів моніторинг пошук найкоротшого шляху хвильовий алгоритм |
| format |
Article |
| author |
Lande, D. V. Berezin, B. A. Pavlenko, O. Yu. |
| author_facet |
Lande, D. V. Berezin, B. A. Pavlenko, O. Yu. |
| author_sort |
Lande, D. V. |
| title |
Algorithm for word segmentation based on the shortest path algorithm inside a graph |
| title_short |
Algorithm for word segmentation based on the shortest path algorithm inside a graph |
| title_full |
Algorithm for word segmentation based on the shortest path algorithm inside a graph |
| title_fullStr |
Algorithm for word segmentation based on the shortest path algorithm inside a graph |
| title_full_unstemmed |
Algorithm for word segmentation based on the shortest path algorithm inside a graph |
| title_sort |
algorithm for word segmentation based on the shortest path algorithm inside a graph |
| title_alt |
Алгоритм сегментации слов на основе поиска кратчайшего пути в графе Алгоритм сегментації слів на основі пошуку найкоротшого шляху в графі |
| description |
The features of word segmentation algorithms from such texts are considered. There are two main models, namely, statistical one and the one using a dictionary. For models with a dictionary, a variant of the maximal matching algorithm is noted for which there are modifications such as Forward Maximal Matching (FMM) and Backward Maximal Matching (BMM) to be depending on the direction of text processing. The second option for models with a dictionary is an algorithm that finds segmentation with a minimum number of words. A new algorithm for words segmenting based on a modified wave algorithm has been presented. The algorithm takes into account the features of the input data and is built in such a way that the necessary calculations are performed in a single pass. This reduces its computational complexity. A description of the word segmentation algorithm is given. An example is shown of splitting an input string in English into words, representing it in the form of a graph and finding the shortest path.To assess the quality of segmentation, the EDWS (Edit Distance of the Word Separator) method is presented. A special tool was used to assess the segmentation of Chinese words with a test corpora based on news texts. Evaluations of the quality of segmentation of words for the proposed algorithm (based on the search for the shortest path) and a number of other known segmentators are obtained. An example of segmentation of a news text in Russian is given. The possibilities of using the developed algorithm in the problems of information search in national resources of the Internet are shown. The implementation of the word segmentation algorithm is used when creating a generalized domain model based on monitoring of the Chinese Internet segment resources.The increase in the number of information resources of the Chinese Internet segment makes it necessary to create of global information retrieval systems. For search indexes of such systems, fast, accurate and complete segmentation of words from texts is necessary. The obtained estimates of segmentation quality using the proposed algorithm for the formation of the search system index indicate the possibility of its use for information resources of the Chinese Internet-segment. |
| publisher |
Інститут проблем реєстрації інформації НАН України |
| publishDate |
2017 |
| url |
http://drsp.ipri.kiev.ua/article/view/142917 |
| work_keys_str_mv |
AT landedv algorithmforwordsegmentationbasedontheshortestpathalgorithminsideagraph AT berezinba algorithmforwordsegmentationbasedontheshortestpathalgorithminsideagraph AT pavlenkooyu algorithmforwordsegmentationbasedontheshortestpathalgorithminsideagraph AT landedv algoritmsegmentaciislovnaosnovepoiskakratčajšegoputivgrafe AT berezinba algoritmsegmentaciislovnaosnovepoiskakratčajšegoputivgrafe AT pavlenkooyu algoritmsegmentaciislovnaosnovepoiskakratčajšegoputivgrafe AT landedv algoritmsegmentacííslívnaosnovípošukunajkorotšogošlâhuvgrafí AT berezinba algoritmsegmentacííslívnaosnovípošukunajkorotšogošlâhuvgrafí AT pavlenkooyu algoritmsegmentacííslívnaosnovípošukunajkorotšogošlâhuvgrafí |
| first_indexed |
2024-04-21T19:33:54Z |
| last_indexed |
2024-04-21T19:33:54Z |
| _version_ |
1796974087934836736 |
| spelling |
drspiprikievua-article-1429172019-12-28T06:17:33Z Algorithm for word segmentation based on the shortest path algorithm inside a graph Алгоритм сегментации слов на основе поиска кратчайшего пути в графе Алгоритм сегментації слів на основі пошуку найкоротшого шляху в графі Lande, D. V. Berezin, B. A. Pavlenko, O. Yu. words segmentation word segmentation quality web resources monitoring shortest path search wave algorithm сегментация слов сегментатор качество сегментации слов мониторинг поиск кратчайшего пути волновой алгоритм сегментація слів сегментатор якість сегментації слів моніторинг пошук найкоротшого шляху хвильовий алгоритм The features of word segmentation algorithms from such texts are considered. There are two main models, namely, statistical one and the one using a dictionary. For models with a dictionary, a variant of the maximal matching algorithm is noted for which there are modifications such as Forward Maximal Matching (FMM) and Backward Maximal Matching (BMM) to be depending on the direction of text processing. The second option for models with a dictionary is an algorithm that finds segmentation with a minimum number of words. A new algorithm for words segmenting based on a modified wave algorithm has been presented. The algorithm takes into account the features of the input data and is built in such a way that the necessary calculations are performed in a single pass. This reduces its computational complexity. A description of the word segmentation algorithm is given. An example is shown of splitting an input string in English into words, representing it in the form of a graph and finding the shortest path.To assess the quality of segmentation, the EDWS (Edit Distance of the Word Separator) method is presented. A special tool was used to assess the segmentation of Chinese words with a test corpora based on news texts. Evaluations of the quality of segmentation of words for the proposed algorithm (based on the search for the shortest path) and a number of other known segmentators are obtained. An example of segmentation of a news text in Russian is given. The possibilities of using the developed algorithm in the problems of information search in national resources of the Internet are shown. The implementation of the word segmentation algorithm is used when creating a generalized domain model based on monitoring of the Chinese Internet segment resources.The increase in the number of information resources of the Chinese Internet segment makes it necessary to create of global information retrieval systems. For search indexes of such systems, fast, accurate and complete segmentation of words from texts is necessary. The obtained estimates of segmentation quality using the proposed algorithm for the formation of the search system index indicate the possibility of its use for information resources of the Chinese Internet-segment. Рассмотрены особенности алгоритмов сегментации слов из текстов, не содержащих разделителей. Представлен новый алгоритм сегментации слов на основе поиска кратчайшего пути. Приведены оценки качества сегментации. Показаны возможности использования приведенного алгоритма в задачах поиска информации в национальных доменах сети Интернет. Реализация алгоритма сегментации слов используется для создания обобщенной модели предметной области на базе мониторинга ресурсов китайского сегмента Интернет. Розглянуто особливості алгоритмів сегментації слів з текстів, які не містять роздільників. Представлено новий алгоритм сегментації слів на основі пошуку найкоротшого шляху. Наведено оцінки якості сегментації. Показано можливості використання наведеного алгоритму в задачах пошуку інформації у національних доменах мережі Інтернет. Реалізацію алгоритму сегментації слів використано для створення узагальненої моделі предметної області на базі моніторингу ресурсів китайського сегменту Інтернет. Інститут проблем реєстрації інформації НАН України 2017-12-26 Article Article application/pdf http://drsp.ipri.kiev.ua/article/view/142917 10.35681/1560-9189.2017.19.4.142917 Data Recording, Storage & Processing; Vol. 19 No. 4 (2017); 3–15 Регистрация, хранение и обработка данных; Том 19 № 4 (2017); 3–15 Реєстрація, зберігання і обробка даних; Том 19 № 4 (2017); 3–15 1560-9189 rus http://drsp.ipri.kiev.ua/article/view/142917/140364 Авторське право (c) 2021 Реєстрація, зберігання і обробка даних |