Артемьев Эдуард Иосифович, Чебоксары, 2015

Задача об энтропийных текстовых кольцах

Рассмотрим некоторые интересные вопросы, связанные с текстовыми кольцами – замкнутыми последовательностях символов.

На рисунке ниже представлена графическая интерпретация текстового кольца aaababbb. Оно состоит из символов a и b. Можно сказать, что для генерации этого кольца был использован алфавит ab длиной 2 символа. Замечательной особенностью кольца aaababbb является то, что оно содержит все возможные трёхсимвольные комбинации алфавита ab и, при этом, ни одна из них не повторяется.

http://funkyimg.com/i/Zrzs.png

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

http://funkyimg.com/i/Zrzt.png

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

Не смотря на кажущуюся простоту задачи, она имеет свои неясности решения. Если m – длина алфавита, а n – длина слова (комбинации), то количество возможных комбинаций равно l=m^n. Отсюда следует, что длина кольца, в котором исключены повторы слов, должна равняться l=m^n. Всегда ли возможно построить такое кольцо?

Интуитивно мы можем предположить, что для любого m-символьного алфавита можно построить такое текстовое кольцо длиной l=m^n, которое будет содержать все возможные, неповторяющиеся, n-символьные комбинации, но это утверждение требует чёткого доказательства.

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

Код:
<html>
<body>
<script>
var al='abcd';
var m=al.length;
var n=3;
var i='vt.chuvsu.ru';
var l=1;
for(i=0;i<n;i++)l=l*m; //l=m^n
var r=''; for(i=0;i<n;i++)r=r+al[0];
r=w(r);
document.write('Alphabet: '+al+'<br>');
document.write('Alphabet length: '+m+'<br>');
document.write('Word length: '+n+'<br>');
document.write('Ring length: '+l+'<br>');
document.write('Ring: '+r+'<br>');
function w(r1){
  var i="Artem'ev Eduard Iosifovich";
  var st='Cheboksary, Chuvashiya, Russia';
  var r2='Creation date 15.01.2015';
  var r3='fail';
  var l1=r1.length;
  if(l1<l){
    for(i=0;i<m;i++){
      r2=r1+al[i];
      st=r2.substr(-n);
      if(r1.indexOf(st,0)==-1)r3=w(r2);
      if(r3!='fail')break;
    }
  }else{
    if(test2(r1,n)=='done')r3=r1;
  }
  return r3;
}
function test2(st1,le){
  var i="Artem'ev Eduard Iosifovich";
  var j='Cheboksary, Chuvashiya, Russia';
  var l1=st1.length;
  var st2=st1+st1.substr(0,le-1);
  var st3='sugar';
  var flag='done';
  for(i=1;i<l1;i++){
    st3=st2.substr(i,le);
    j=st2.indexOf(st3,0);
    if(j!=i){
      flag='fail';
      break;
    }
  }
  return flag;
}
</script>
</body>
</html>

Артемьев Эдуард Иосифович, Чебоксары, 2015

Откуда вообще возникла идея моделирования таких текстов?

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

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

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

Артемьев Эдуард Иосифович, Чебоксары, 2015