О числе реконструкций по подсловам в бинарном алфавите при наложении на один символ

  • Galina Nikolaevna Zhukova Национальный исследовательский университет "Высшая школа экономики" http://orcid.org/0000-0003-1835-7422
  • Yuri Gennadievich Smetanin Федеральный исследовательский центр "Информатика и управление" РАН http://orcid.org/0000-0003-0242-6972
  • Mikhail Vasilevich Ulyanov Институт проблем управления им. В.А. Трапезникова РАН; Московский государственный университет имени М.В. Ломоносова http://orcid.org/0000-0002-5784-9836

Аннотация

Рассмотрена задача получения точных оценок числа реконструкций для слов над бинарным алфавитом. Подслова различной длины из заданного множества соединяются методом наложения концевых символов. Соединять можно только такую пару подслов, у которых последний символ первого подслова совпадает с первым символом второго. При наложении пары подходящих подслов на один символ из двух одинаковых символов (в конце первого и в начале второго подслова) в реконструкцию входит только один. Предложен подход, основанный на рассмотрении усеченных подслов, состоящих из префикса и суффикса данного подслова, имеющих длину один. При построении реконструкции вместо самих подслов из заданного множества соединяются усеченные слова вида "00", "01", "10" и "11". Число реконструкций находится в предположении, что каждое из усеченных подслов соответствует уникальному подслову в заданном множестве подслов. В результате при соединении слов "00" и "00" возможны две реконструкции, соответствующие соединению исходных подслов "0x0" и "0y0" в "0x0y0" и "0y0x0", где x и y — различные последовательности символов бинарного алфавита, одна из которых может быть пустой (но не обе одновременно).
Такой подход позволил определить условия существования реконструкции по заданному множеству подслов различной длины. Показано, при каких условиях, касающихся количества усеченных подслов каждого вида, реконструкция невозможна. Например, невозможна реконструкция по множеству подслов, содержащему только подслова вида "00" и "11". Также невозможно соединить все подслова заданного множества, если число усеченных подслов вида "01" и "10" отличается больше, чем на один. Для различных случаев, допускающих полную реконструкцию, получены формулы точного числа реконструкций. Точное число реконструкций зависит от наличия или отсутствия подслов, соответствующих усеченным подсловам каждого вида.
Поскольку возможность реконструкции главным образом зависит от соотношения числа подслов вида "01" и "10", то отдельно была рассмотрена модель с возможностью инверсий слов. Предполагается, что множество подслов для реконструкции содержит только слова вида вида "00", "01" "00", Часть слов вида "01" записывается в обратном порядке и становится словами вида "10". Если слов "01" было четное число, то в "01" преобразуется половина слов "01", иначе — половина от ближайшего четного числа. В последнем случае из множества подслов вида «01» получается два варианта наборов подслов вида "01" и "10", в одном больше подслов "01", в другом — "10". Для каждого случая приведены формулы точного числа реконструкций при условии уникальности подслов в заданном множестве, а также несимметричности подслов, порождающих усеченные подслова вида "00" и "11".

Сведения об авторах

Galina Nikolaevna Zhukova, Национальный исследовательский университет "Высшая школа экономики"

доцент Департамента программной инженерии, факультет компьютерных наук, кандидат физико-математических наук, доцент

Yuri Gennadievich Smetanin, Федеральный исследовательский центр "Информатика и управление" РАН

главный научный сотрудник Вычислительного центра им. А.А. Дородницына РАН, доктор физико-математических наук

Mikhail Vasilevich Ulyanov, Институт проблем управления им. В.А. Трапезникова РАН; Московский государственный университет имени М.В. Ломоносова

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

Литература

[1] Lothaire M. Combinatorics on Words. In: Encyclopedia of Mathematics and its Applications. vol. 17. Addison-Wesley, Reading, Mass; 1983. (In Eng.)
[2] Lothaire M. Algebraic Combinatorics on Words. Cambridge: Cambridge University Press; 2002. (In Eng.) DOI: https://doi.org/10.1017/CBO9781107326019
[3] Lothaire M. Applied Combinatorics on Words. In: Encyclopedia of Mathematics and its Applications. Cambridge: Cambridge University Press; 2005. (In Eng.)
[4] Berstel J., Karhumäki J. Combinatorics on Words – A Tutorial . Bulletin of the European Association for Theoretical Computer Science. 2003; 79:178-228. Available at: https://eatcs.org/images/bulletin/beatcs79.pdf (accessed 27.05.2020). (In Eng.)
[5] Kahrumäki J. Combinatorics on Words: A New Challenging Topic. Technical Report no. 645. Turku Center for Computer Science; 2004. Available at: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.537.1828&rep=rep1&type=pdf (accessed 27.05.2020). (In Eng.)
[6] Berstel J., Perrin D. The origins of combinatorics on words. European Journal of Combinatorics. 2007; 28(3):996-1022. (In Eng.) DOI: https://doi.org/10.1016/j.ejc.2005.07.019
[7] Blanchet-Sadri F. Algorithmic Combinatorics on Partial Words. Chapman & Hall/CRC; 2007. (In Eng.) DOI: https://doi.org/10.1201/9781420060935
[8] Lascoux A., Schützenberger M.P. A New Statistics on Words. Annals of Discrete Mathematics. 1980; 6:251-255. (In Eng.) DOI: https://doi.org/10.1016/S0167-5060(08)70709-X
[9] Lascoux A., Schützenberger M.-P. Sur une conjecture de H.O. Foulkes. C. R. Acad. Sci. Paris. 1978; 286 A(7):323-324. Available at: http://www-igm.univ-mlv.fr/~berstel/Mps/Travaux/A/1978-4FoulkesCras.pdf (accessed 27.05.2020). (In French)
[10] Reutenauer C., Schützenberger M.P. Rational word functions: Characterization and minimization. In: M. Ito (ed.) Words, Languages and Combinatorics. Proceedings of the International Colloquium. Kyoto, Japan, 28-31 August 1990. World Sci. Publishing, River Edge, NJ; 1992. p. 435-443. Available at: http://www-igm.univ-mlv.fr/~berstel/Mps/Travaux/A/1992-3ChristopheKyoto.pdf (accessed 27.05.2020). (In Eng.)
[11] Levenshtein V.I. Maximum Number of Words in Codes without Overlaps. Problemy Peredachi Informatsii = Problems of Information Transmission. 1970; 6(4):355-357. (In Eng.)
[12] Levenshtein V.I. Upper-Bound Estimates for Fixed-Weight Codes. Problemy Peredachi Informatsii = Problems of Information Transmission. 1971; 7(4):281-287. (In Eng.)
[13] Dress A.W.M., Erdős P.L. Reconstructing Words from Subwords in Linear Time. Annals of Combinatorics. 2005; 8(4):457-462. (In Eng.) DOI: https://doi.org/10.1007/s00026-004-0232-4
[14] Gamow G. Combinatorial Principles in Genetics. In: E.F. Beckenbach, G. Pólya (ed.) Applied Combinatorial Mathematics. New York, J. Wiley; 1964. p. 515-535. (In Eng.)
[15] Jonoska N., Saito M. (eds.) Discrete and Topological Models in Molecular Biology. Natural Computing Series. Springer, Berlin, Heidelberg; 2014. (In Eng.) DOI: https://doi.org/10.1007/978-3-642-40193-0
[16] Erdős P.L., Ligeti P., Sziklai P., Torney D.C. Subwords in Reverse-Complement Order. Annals of Combinatorics. 2006; 10(4):415-430. (In Eng.) DOI: https://doi.org/10.1007/s00026-006-0297-3
[17] Herbelot A., Baroni M. High-risk learning: acquiring new word vectors from tiny data. In: Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing (EMNLP-2017). Copenhagen, Denmark, Association for Computational Linguistics; 2017. p. 304-309. (In Eng.) DOI: https://doi.org/10.18653/v1/D17-1030
[18] Bojanowski Р., Grave Е., Joulin A., Mikolov T. Enriching Word Vectors with Subword Information. Transactions of the Association for Computational Linguistics. 2017; 5:135-146. Available at: https://transacl.org/ojs/index.php/tacl/article/view/999 (accessed 27.05.2020). (In Eng.)
[19] Pinter Y., Guthrie R., and Eisenstein J. Mimicking Word Embeddings using Subword RNNs. In: Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing (EMNLP-2017). Copenhagen, Denmark, Association for Computational Linguistics; 2017. p. 102-112. (In Eng.) DOI: https://doi.org/10.18653/v1/D17-1010
[20] Zhao J., Mudgal S., Liang Y. Generalizing Word Embeddings using Bag of Subwords. In: Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing (EMNLP-2018). Brussels, Belgium, Association for Computational Linguistics; 2018. p. 601-606. (In Eng.) DOI: https://doi.org/10.18653/v1/D18-1059
[21] Sasaki S., Suzuki J., Inui K.. Subword-based Compact Reconstruction of Word Embeddings. In: Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers) (NAACL-2019). Minneapolis, Minnesota, Association for Computational Linguistics; 2019. p. 3498-3508. (In Eng.) DOI: https://doi.org/10.18653/v1/N19-1353
[22] Pennington J., Socher R., and Manning C. GloVe: Global Vectors for Word Represqentation. In: Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP-2014). Doha, Qatar, Association for Computational Linguistics; 2014. p. 1532-1543. (In Eng.) DOI: https://doi.org/10.3115/v1/D14-1162
[23] Mikolov T., Chen K., Corrado G., Dean J. Efficient Estimation of Word Representations in Vector Space. arXiv:1301.3781. Available at: https://arxiv.org/abs/1301.3781 (accessed 27.05.2020). (In Eng.)
[24] Smetanin Y.G., Ulyanov M.V. Reconstruction of a Word from a Finite Set of its Subwords under the unit Shift Hypothesis. I. Reconstruction without for Bidden Words. Cybernetics and Systems Analysis . 2014; 50(1):148-156. (In Eng.) DOI: https://doi.org/10.1007/s10559-014-9602-z
[25] Smetanin Y.G., Ulyanov M.V. Reconstruction of a Word from a Finite Set of its Subwords Under the Unit Shift Hypothesis. II. Reconstruction with Forbidden Words. Cybernetics and Systems Analysis . 2015; 51(1):157-164. (In Eng.) DOI: https://doi.org/10.1007/s10559-015-9708-y
[26] Smetanin Y., Ulyanov M., Shulga M. On Calculating the Entropy of 2D Words Over a Finite Alphabet. In: 2018 International Conference on Engineering Technologies and Computer Science (EnT-2018). Moscow; 2018. p. 82-85. (In Eng.) DOI: https://doi.org/10.1109/EnT.2018.00025
[27] Ulyanov M., Smetanin Y. Entropy Function of Finite Words . In: 2017 International Workshop on Engineering Technologies and Computer Science (EnT-2017). Moscow; 2017. p. 8-11. (In Eng.) DOI: https://doi.org/10.1109/EnT.2017.7
Опубликована
2020-09-30
Как цитировать
ZHUKOVA, Galina Nikolaevna; SMETANIN, Yuri Gennadievich; ULYANOV, Mikhail Vasilevich. О числе реконструкций по подсловам в бинарном алфавите при наложении на один символ. Международный научный журнал «Современные информационные технологии и ИТ-образование», [S.l.], v. 16, n. 2, p. 304-313, sep. 2020. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/650>. Дата доступа: 22 oct. 2021 doi: https://doi.org/10.25559/SITITO.16.202002.304-313.
Раздел
Теоретические вопросы информатики, прикладной математики, компьютерных наук

Наиболее читаемые статьи этого автора (авторов)