Алгоритм для преобразования диапазона номеров в регулярное выражение

#алгоритм #регулярные_выражения #любой_язык

Не знаю, насколько правильно выглядит сам заголовок, но подробнее опишу здесь.

Итак, суть такова: есть, к примеру, некий диапазон и пара условий:  


$start и $end всегда имеют одинаковую символьную длину (хотя это и не столь важно);
И если есть диапазон, включающий в себя элемент 555123456 (длина 9 символов), то
нет никакого другого диапазона, который включал бы в себя номер, превосходящий по длине
уже имеющийся и начинающийся с 555 - т.е. номер 5551234567 (длина - 10 символов) не
существует по определению.
Последние цифры в $start и $end равняются 0 и 9 соответственно, что тоже облегчает
задачу.


Т.е. (здесь и далее пишу условно, без привязки к каким-либо языку программирования
или стандарту regexp)

555000000 - 555999999 // Т.е. 555*
666000000 - 666999999 // Т.е. 666*

5550000000 - 5559999999 // Не существует в списке диапазонов по определению задачи,
игнорируем.
6660000000 - 6669999999 // Не существует в списке диапазонов по определению задачи,
игнорируем.


Иными словами: если задан 555000000 - 555999999, то нет 5550000000 - 5559999999

Возьмем, например

555000000 - 555999999


Задача: преобразовать в 555*. С указанным примером разобраться несложно - необходимо
отнять $start от $end, чтобы получить некую переменную $result, которая равна 999999.
Затем использовать значение результата операции $result.length() по отношению к, скажем,
$start, чтобы получить строку 555*

$shortrec = substr($start,0,-strlen($result)) . "*";


Но если диапазон выглядит как

777120000 - 777259999


то разница будет иметь значение 139999. Здесь сложнее, но тоже понятно - помимо отчасти
указанного выше, сравниваем позиции 0 и 9 в обеих переменных, "выходим" на 12 и дополнительно
обрабатываем 12, наращивая его 13 раз и получая в цикле следующую последовательность: 

77712*
77713*
77714*
...
77725*


Но как быть, если есть диапазон,

888125120 - 888959599


(здесь вспомним облегчающее логику условие номер 3, чтобы не оперировать выражением
типа [5-9], если бы $start равнялся бы 888125125) для которого необходимо получить

88812512*
8882*
8883*
...
8888*

88890*
88891*
88892*
...
88894*

888950*
888951*
888952*
...
888958*

8889590*
8889591*
8889592*
...
8889595*



Прошу рассудить - следую ли я с самого начала правильной логике или нет?
И есть ли некоторое универсальное решение (алгоритм) для подобных задач?
Как поступили бы вы?


P.S. Язык программирования не важен - важен сам подход и алгоритм. Надеюсь, не сломал
читающему мозг, но задача не из учебных, а самая что ни на есть настоящая. Так что
если есть идеи, буду весьма признателен.
    

Ответы

Ответ 1

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


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


На примере понятнее, что все это обозначает. Исходный диапазон 14-123456 разбиваем
на три диапазона 14-99, 100-99999, 100000-123456.
Если присутствует второй диапазон, то он задается простым выражением \d{n,m}, первый
и второй диапазон нужно генерировать отдельно и в границах этих диапазонов всегда одинаковое
количество знаков, а значит применим основной алгоритм генерации, а затем объединим
эти 3 диапазона альтернативой.  

Основной алгоритм для диапазонов с одинаковым количеством цифр


Попытаемся найти общую часть для верхней и нижней границы. Например в диапазоне 1234-1278
можно вынести 12 как обычные символы.  
Начнем просмотр границ слева-направо. Для примера диапазон 1234-5678  
Первые цифры нижней и верхней границ 1 и 5, поэтому разделим на 3 диапазона: 1234-1999,
2000-4999, 5000-5678, то есть как бы выделим середину, которую можно представить как
[2-4]\d{3}    
Оставшиеся два диапазона обработаем по тому же самому алгоритму. Например для 1234-1999
сперва вынесем цифру 1 как общую. Диапазон 234-999 разобьем на 2 диапазона 234-299, 300-999
И так далее для всех диапазонов, которые появятся в ходе разбиения на составные диапазоны.


Кода безумно много, но зато можно запустить и потестировать.



$( document ).ready( function() {
  $( "#rangeLeft, #rangeRight" ).keydown( function() {
    clearDisplay();
  } );
  $( "#run" ).click( function() {
    clearDisplay();
    var rangeLeft = $( "#rangeLeft" ).val();
    var rangeRight = $( "#rangeRight" ).val();
    if ( ! checkRanges( rangeLeft,  rangeRight ) ) return;
    $( "#result" ).append( generateFullRegExp(rangeLeft, rangeRight)+"
" );
    $( "#test" ).show();
  } );
  $( "#test" ).click( function() {
    var rangeLeft = $( "#rangeLeft" ).val();
    var rangeRight = $( "#rangeRight" ).val();
    var re = new RegExp( "^"+generateFullRegExp(rangeLeft, rangeRight)+"$" );
    for( var i=Math.pow( 10, rangeLeft.length-1 ); iparseInt(rangeRight) )
) $( "#result" ).append( "Тест провален на: " + i+"
" );
      if ( !re.test( i+"" ) && ( i>parseInt(rangeLeft) && i" );
    };
    $( "#result" ).append( "Тест пройден от "+Math.pow( 10, rangeLeft.length-1 )+"
до "+i+"
" );
  } );
} );

function checkRanges( rangeLeft, rangeRight ) {
  if ( /\D/.test( rangeLeft ) || /\D/.test( rangeRight ) ) {
    $( "#result" ).append( "Введите два числа
" );
    return false;
  };
  rangeLeft = parseInt( rangeLeft );
  rangeRight = parseInt( rangeRight );
  if ( isNaN( rangeLeft ) || isNaN( rangeRight ) ) $( "#result" ).append( "Не указаны
границы диапазонов
" );
  if ( rangeLeft < 0 ) $( "#result" ).append( "Левая граница меньше 0
" );
  if ( rangeRight < 0 ) $( "#result" ).append( "Правая граница меньше 0
" );
  if ( rangeLeft > rangeRight ) $( "#result" ).append( "Левая граница больше правой
границы
" );
  return( !(
    rangeLeft < 0 ||
    rangeRight < 0 ||
    rangeLeft > rangeRight ||
    isNaN( rangeLeft ) ||
    isNaN( rangeRight )
  ) );
};

function maxBeginStr( str1, str2 ) {
  var res = /^(.*)[^-]*\-\1/.exec( str1 + "-" + str2 );
  return res ? res[1] : "";
};

function midDiap( start, end ){
  var st0int = parseInt( start[0] );
  var en0int = parseInt( end[0] );
  if ( st0int+1 == en0int ) {
    var res = end[0];
  } else {
  	if ( st0int == en0int-2 ) {
  		res=( st0int+1 )+"";
  	} else {
  		res="["+( st0int+1 )+"-"+(en0int-1)+"]";
  	};
  };
  if ( start.length == 1 ) return res;
  return res+"\\d{"+(start.length-1)+"}";
};

function lowDiap( num, pos ) {
  var res = num.substr(0, pos);
  var highRange = parseInt( num[pos] )-1;
  if ( highRange == -1 && pos == num.length-1 ) return num;
  if ( highRange == -1 ) return null; // выражение можно не включать
  if ( pos == num.length-1 ) highRange++;
  res += "[0-"+highRange+"]";
  if ( num.length != pos+1 ){
    res += "\\d{"+(num.length-pos-1)+"}";
  }
  return res;
};

function highDiap( num, pos ) {
  var res = num.substr(0, pos);
  var lowRange = parseInt( num[pos] )+1;
  if ( lowRange==10 && pos == num.length-1 ) return num;
  if ( lowRange==10 ) return null; // выражение можно не включать
  if ( pos == num.length-1 ) lowRange--;
  res += "["+lowRange+"-9]";
  if ( num.length != pos+1 ){
    res += "\\d{"+( num.length -pos-1)+"}";
  }
  return res;
};

function getRegExp( start, end ) {
    if ( start.length != end.length ) return "Invalid input";
    var res= maxBeginStr( start, end );
    start= start.substr( res.length ); 
    end  = end.substr( res.length );
    if ( start.length  == 0 ) return res;
    var st0int = parseInt( start[0] );
    var en0int = parseInt( end[0] );
    var resArr= Array(); 
    if ( start.length > 1 ) {
      if ( st0int != en0int-1 ) {
        resArr.push( midDiap( start, end) );
      }
      for ( var i=1; i 1 ) resArr.push( ("\\d{"+(rangeLeft.length+1)+","+(rangeRight.length-1)+"}").replace(/(\d+),\1/,
"$1") );
  resArr.push( getRegExp( "1"+"0".repeat( rangeRight.length-1 ), rangeRight ) );
  return "(?:"+resArr.join("|")+")";
};

function clearDisplay() {
  $( "#result" ).html( "" );
  $( "#test" ).hide();
};
#test { display:none }

  
     - 
    

    
    

    
  




Существующий недочет
Для диапазона 10-29 и.т.п. сгенерируется избыточное выражение (?:2[0-9]|1[0-9])


Ответ 2

Т.к. границы диапозонов имеют одинаковую разрядность, то можно использовать такой
способ преобразования диапозона в регулярку - это поразрядное сравнение границ и генерации
ретроспективных проверок на все предыдущие разряды относительно текущей позиции.
Для диапозона 813 - 895 выражение будет например таким:
8[1-9](?:(?<=1)[3-9]|(?<=[2-8])[0-9]|(?<=9)[0-5])

Обратите внимание, что здесь рассматривается три случая относительно среднего разряда:

Значение равно нижней границе - 1, значит текущее значение не может быть меньше 3.
Значение между нижней и верхней границами, значит текущее значение может быть любой
цифрой.
Значение равно верхней границе - 9, значит текущее значение не может быть больше 5.

Чем выше разрядность, тем сложнее получится конечное регулярное выражение, т.к. для
каждого младшего разряда нужно выполнять ретроспективные проверки для всех старших
разрядов.


Ответ 3

Я бы сделал рекурсивный спуск: (C#)

IEnumerable GetPatterns(string start, string end)
{
    if (start.Length == 0)
    {
        yield return "";
        yield break;
    }
    var startPrefix = start.Substring(0, start.Length - 1);
    var endPrefix = end.Substring(0, end.Length - 1);

    var startSuffix = start.Last();
    var endSuffix = end.Last();

    var rec = GetPatterns(startPrefix, endPrefix).ToList();
    for (int i = 0; i < rec.Count; i++)
    {
        char startDigit = (i == 0) ? startSuffix : '0';
        char endDigit = (i == rec.Count - 1) ? endSuffix : '9';

        if (startDigit == '0' && endDigit == '9')
        {
            yield return rec[i] + '*';
        }
        else
        {
            for (var digit = startDigit; digit <= endDigit; digit++)
                yield return rec[i] + digit;
        }
    }
}


Проверка: http://ideone.com/xihhpr

Обратите внимание на результат для промежутка 5050000-5959999 — вам надо такое, или нет?