О числе реконструкций по подсловам в бинарном алфавите при наложении на один символ
Аннотация
Рассмотрена задача получения точных оценок числа реконструкций для слов над бинарным алфавитом. Подслова различной длины из заданного множества соединяются методом наложения концевых символов. Соединять можно только такую пару подслов, у которых последний символ первого подслова совпадает с первым символом второго. При наложении пары подходящих подслов на один символ из двух одинаковых символов (в конце первого и в начале второго подслова) в реконструкцию входит только один. Предложен подход, основанный на рассмотрении усеченных подслов, состоящих из префикса и суффикса данного подслова, имеющих длину один. При построении реконструкции вместо самих подслов из заданного множества соединяются усеченные слова вида "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".
Литература
[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
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
