Метод вилучення помилкових збігів текстів в електронних документах

Заголовок (російською):

Метод исключения ошибочных совпадений текстов в электронных документах

Заголовок (англійською):

The method of elimination of erroneous coincidences text in electronic documents

Автор(и):

Білощицький А.О.

Криштоф С.Д.

Білощицька С.В.

Діхтяренко О.В.

Автор(и) (англ):

Biloshchytskyi, A.

Kristof, S.

Biloshchytska, S.

Dikhtiarenko, O.

Ключові слова (укр):

хеш-функції; хешування; шингли; перевірка збігів; плагіат

Ключові слова (рус):

хэш-функции; хеширование; шинглы; проверка совпадений; плагиат

Ключові слова (англ):

a hash-function; hashing; shingles; test matches; plagiarism

Анотація (укр):

Розглянуто модель збігу та метод визначення нечітких збігів у тексті, на їх основі запропоновано метод вилучення помилкових збігів текстів у документах, що перевіряються. Показано, що за рахунок використання методу локально-чутливої хеш-функції знаходження нечітких збігів можна отримати кращий результат, ніж при використанні криптографічної хеш-функції. Оскільки зі збільшенням повноти охоплення точок страждає точність методу, було розроблено метод фільтрації помилкових збігів, який базується на припущенні, що справжні збіги між елементами індексу обов’язково будуть з’являтися на незначній відстані один від одного (відстань – різниця номерів елементів індексу), причому одна група збігів повинна мати незначні відстані як в документі, що перевіряється, так і в документі, з яким перевіряється. Розроблений метод використовує Декартову площину та оптимізований спосіб розрахунку відстаней між елементами для вилучення помилкових результатів і визначення нечітких збігів.

Анотація (рус):

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

Анотація (англ):

The article describes a model and matching method for determining fuzzy matches in the text on the basis of their proposed method of extracting false matches text in scanned documents. It is shown that by using the method of locally sensitive hash finding fuzzy matches will get better results than using a cryptographic hash function. But with the increasing suffering of completeness accuracy of the method. Therefore, we developed a method of filtration of false matches, which is based on the assumption that these coincidences between the elements of the index is required to appear at a slight distance from each other (the distance - the difference between the numbers of elements of the index), and one group matches should have a slight distance in the document that checked, and the document, which is checked. The developed method uses a Cartesian plane and optimized method of calculating the distance between the elements to discard false positives and identify fuzzy matches. The method of extraction of false matches text in a document scanned in information technology determining fuzzy matches based on the hypothesis that these matches have to be next to each other. The word "near" is meant that the relevant text fragments shingles that match, should be at a small distance from each other in the source code.

Публікатор:

Київський національний університет будівництва і архітектури

Назва журналу, номер, рік випуску (укр):

Управління розвитком складних систем, номер 22, частина 1, 2015

Назва журналу, номер, рік випуску (рус):

Управление развитием сложных систем, номер 22, часть 1, 2015

Назва журналу, номер, рік випуску (англ):

Management of Development of Complex Systems, number 22, part 1, 2015

Мова статті:

Українська

Формат документа:

application/pdf

Документ:

144-150.pdf

Дата публікації:

24 Апрель 2015

Номер збірника:

Розділ:

ІНФОРМАТИЗАЦІЯ ВИЩОЇ ОСВІТИ

Університет автора:

Київський національний університет будівництва і архітектури, Київ; Міністерство освіти і науки України, Київ

Литература:

1. Закон України «Про авторське право і суміжні права» № 3729-12 від 05.12.2012, підстава 5460-17

2. Білощицький, А.О. Ефективність методів пошуку збігів у текстах / А.О. Білощицький, О.В. Діхтяренко // Управління розвитком складних систем. – 2013. – № 14.– С. 144 – 147.

3. Ke, Y., Sukthankar, R., Huston, L., Ke, Y., & Sukthankar, R. (2004, October). Efficient near-duplicatedetectionand sub-imageretrieval. In ACM Multimedia (Vol. 4, No. 1, p. 5).

4. Lv, X., & Wang, Z. J. (2012). Perceptual image hashing based on shape contexts and local feature points. Information Forensics and Security, IEEE Transactions on, 7(3), 1081-1093.

5. Hamming, R. W. (1950). Error detecting and error correcting codes. Bell System technical journal, 29(2), 147-160.

6. Chum, O., Philbin, J., &Zisserman, A. (2008, September). NearDuplicateImageDetection: min-Hash and tf-idfWeighting. In BMVC (Vol. 810, pp. 812-815).

7. Leskovec, J., Rajaraman, A., &Ullman, J. D. (2014). Miningofmassivedatasets. CambridgeUniversityPress.

8. Platter W., Phashion, (2014), GitHubrepository, https://github.com/westonplatter/phashion

9. Білощицький А.О. Оптимізація системи пошуку збігів за допомогою використання алгоритмів локально чутливого хешування наборів текстових даних/ А.О. Білощицький, О.В. Діхтяренко // Управління розвитком складних систем. – 2014. – № 19.– С. 113 – 117.

10. Гогунский, В.Д. Обоснование закона о конкурентных свойствах проектов / В.Д. Гогунский, С.В. Руденко,
П.А. Тесленко // Управління розвитком складних систем. –2011. – № 8. – С. 14 – 16.

11. Оборський, Г.О. Стандартизація і сертифікація процесів управління якістю освіти у вищому навчальному закладі / Г.О. Оборський, В.Д. Гогунський, О.С. Савельєва // Тр. Одес. политехн. ун-та. –2011. – № 1(35). – С. 251 – 255.

12. Колесникова, Е.В. Моделирование слабо структурированных систем проектного управления / Е.В. Колесникова // Тр.Одес. политехн. ун-та. – 2013. ‑ № 3 (42). – С. 127 – 131.

13. Колесникова, Е.В. Трансформация когнитивных карт в модели марковских процессов для проектов создания программного обеспечения / Е.В. Колесникова, А.А. Негри // Управління розвитком складних систем. ‑ 2013. – №15.
– C. 30 – 35.

14. Vaysman, V. A. The planar graphs closed cycles determination method / V. A. Vaysman, D. V. Lukianov, K. V. Kolesnikova // Тр. Одес. политехн. ун-та. – 2012. – № 1(38). – С. 222 – 227.

15. Burkov, V. N., Biloshchytskyi, A. A., & Gogunsky, V. D. (2013). Options citation of scientific publications in scientometric databases. Management of development of difficult systems. Kyiv, Ukraine: KNUCA, 15, 134 - 139.

16. Gogunsky, V. D., Kolyada, A. S., & Iakovenko, V. O. (2014). Scientometric data scientific publication "Management of development of difficult systems. Management of development of difficult systems. Kyiv, Ukraine: KNUCA, 19, 6 – 11.

17. Vlasenko, O. V., Lebed’ V. V., & Gogunsky, V. D. (2012). Markov model of communication processes in international projects. Management of development of difficult systems. Kyiv, Ukraine: KNUCA: 12, 35 ‑ 39.

Gogunsky, V. D., Iakovenko, V. O., & Kolyada, A. S. (2014). Application of Latent Dirichlet allocation for the analysis of scientometric publications database. Proc. of Odes. Polytechnic. Univ. Odessa, Ukraine, ONPU: 1 (43), 186 – 191.

References:

1. The law of Ukraine on copyright and related rights № 3729-12 on 05.12.2012

2. Biloshchytskyi, A., & Dikhtiarenko, O. (2013). The effectiveness of methods for finding matches in texts. Management of complex systems, 14, pp. 144 – 147.

3. Ke, Y., Sukthankar, R., Huston, L., Ke, Y., & Sukthankar, R. (2004, October). Efficient near-duplicate detection and sub-image retrieval. In ACM Multimedia (Vol. 4, No. 1, p. 5).

4. Lv, X., & Wang, Z. J. (2012). Perceptual image hashing based on shape contexts and local feature points. Information Forensics and Security, IEEE Transactions on, 7(3), 1081-1093.

5. Hamming, R. W. (1950). Error detecting and error correcting codes. Bell System technical journal, 29(2), 147-160.

6. Chum, O., Philbin, J., & Zisserman, A. (2008, September). Near Duplicate Image Detection: min-Hash and tf-idf Weighting. In BMVC (Vol. 810, pp. 812-815).

7. Leskovec, J., Rajaraman, A., & Ullman, J. D. (2014). Mining of massive datasets. Cambridge University Press.

8. Platter W., & Phashion, (2014), GitHub repository, https://github.com/westonplatter/phashion.

9. Biloshchytskyi, A., & Dikhtiarenko, O. (2014). Optimization of Matching algorithms by using local-sensitive hash sets of text data. Management of complex systems, 19, pp. 113 – 117.

10. Gogunsky, V. D., Rudenko, S. V., & Teslenko, P. A. (2012). Justification law on competitive properties of projects. Management of development of difficult systems. Kyiv, Ukraine, KNUCA: 8, 14 ‑ 16.

11. Oborsky, G. A., Gogunsky, V. D., & Saveleva O. S. (2011). Standardization and certification processes of the quality management education in higher education. Proceedings of Odes. Polytechnic. Univ, 1 (35), 251 – 255.

12. Kolesnikova, K. V. (2013). Modeling weakly structured project management systems. Proceedings of Odes. Polytechnic. Univ, 3 (42), 127 – 131.

13. Kolesnikova, K. V., & Negri, A. A. (2013). Transformation of cognitive maps in the model of Markov processes for projects creating software. Management of development of difficult systems. Kyiv, Ukraine: KNUCA, 15, 30 – 35.

14. Vaysman, V. A. Lukianov, D. V. & Kolesnikova, K. V. (2012). The planar graphs closed cycles determination method. Proceedings of Odes. Polytechnic. Univ, 1(38), 222 – 227.

15. Burkov, V. N., Biloshchytskyi, A. A., & Gogunsky, V. D. (2013). Options citation of scientific publications in scientometric databases. Management of development of difficult systems. Kyiv, Ukraine: KNUCA, 15, 134 – 139.

17. Vlasenko, O. V., Lebed’ V. V., & Gogunsky, V. D (2012). Markov model of communication processes in international projects. Management of development of difficult systems. Kyiv, Ukraine: KNUCA: 12, 35 ‑ 39.

18. Gogunsky, V. D., Iakovenko, V. O., & Kolyada, A. S. (2014). Application of Latent Dirichlet allocation for the analysis of scientometric publications database. Proc. of Odes. Polytechnic. Univ. Odessa, Ukraine, ONPU: 1 (43), 186 – 191.