[Se c'è bisogno di questo perché è qualche sistema 3rd party strano che richiede regexp]
nuovo approccio
il più ci penso Frederik di commento, più sono d'accordo. il motore regexp dovrebbe essere in grado di compilarlo in un DFA compatto, anche se la stringa di input è lunga. per molti casi, la seguente è una soluzione ragionevole:
import re
def regexp(lo, hi):
fmt = '%%0%dd' % len(str(hi))
return re.compile('(%s)' % '|'.join(fmt % i for i in range(lo, hi+1)))
(funziona bene con tutti gli intervalli numerici nelle prove di seguito, inclusi 99.519.000 - 99519099. un calcolo back-of-the-busta ruvida suggerisce che 9 i numeri delle cifre sono circa il limite con 1 GB di memoria, cioè se la maggior parte dei numeri di quella dimensione è abbinata, se solo alcuni sono abbinati puoi andare molto più grande.).
vecchio approccio
[aggiornato di nuovo per dare risultati ancora più brevi - a parte coalescenza l'occasionale \d\d è circa buono come la mano-generata]
assumendo tutti i numeri sono la stessa lunghezza (si es nullo pad a sinistra se necessario), questo funziona:
import re
def alt(*args):
'''format regexp alternatives'''
if len(args) == 1: return args[0]
else: return '(%s)' % '|'.join(args)
def replace(s, c):
'''replace all characters in a string with a different character'''
return ''.join(map(lambda x: c, s))
def repeat(s, n):
'''format a regexp repeat'''
if n == 0: return ''
elif n == 1: return s
else: return '%s{%d}' % (s, n)
def digits(lo, hi):
'''format a regexp digit range'''
if lo == 0 and hi == 9: return r'\d'
elif lo == hi: return str(lo)
else: return '[%d-%d]' % (lo, hi)
def trace(f):
'''for debugging'''
def wrapped(lo, hi):
result = f(lo, hi)
print(lo, hi, result)
return result
return wrapped
#@trace # uncomment to get calls traced to stdout (explains recursion when bug hunting)
def regexp(lo, hi):
'''generate a regexp that matches integers from lo to hi only.
assumes that inputs are zero-padded to the length of hi (like phone numbers).
you probably want to surround with^and $ before using.'''
assert lo <= hi
assert lo >= 0
slo, shi = str(lo), str(hi)
# zero-pad to same length
while len(slo) < len(shi): slo = '0' + slo
# first digits and length
l, h, n = int(slo[0]), int(shi[0]), len(slo)
if l == h:
# extract common prefix
common = ''
while slo and slo[0] == shi[0]:
common += slo[0]
slo, shi = slo[1:], shi[1:]
if slo: return common + regexp(int(slo), int(shi))
else: return common
else:
# the core of the routine.
# split into 'complete blocks' like 200-599 and 'edge cases' like 123-199
# and handle each separately.
# are these complete blocks?
xlo = slo[1:] == replace(slo[1:], '0')
xhi = shi[1:] == replace(shi[1:], '9')
# edges of possible complete blocks
mlo = int(slo[0] + replace(slo[1:], '9'))
mhi = int(shi[0] + replace(shi[1:], '0'))
if xlo:
if xhi:
# complete block on both sides
# this is where single digits are finally handled, too.
return digits(l, h) + repeat('\d', n-1)
else:
# complete block to mhi, plus extra on hi side
prefix = '' if l or h-1 else '0'
return alt(prefix + regexp(lo, mhi-1), regexp(mhi, hi))
else:
prefix = '' if l else '0'
if xhi:
# complete block on hi side plus extra on lo
return alt(prefix + regexp(lo, mlo), regexp(mlo+1, hi))
else:
# neither side complete, so add extra on both sides
# (and maybe a complete block in the middle, if room)
if mlo + 1 == mhi:
return alt(prefix + regexp(lo, mlo), regexp(mhi, hi))
else:
return alt(prefix + regexp(lo, mlo), regexp(mlo+1, mhi-1), regexp(mhi, hi))
# test a bunch of different ranges
for (lo, hi) in [(0, 0), (0, 1), (0, 2), (0, 9), (0, 10), (0, 11), (0, 101),
(1, 1), (1, 2), (1, 9), (1, 10), (1, 11), (1, 101),
(0, 123), (111, 123), (123, 222), (123, 333), (123, 444),
(0, 321), (111, 321), (222, 321), (321, 333), (321, 444),
(123, 321), (111, 121), (121, 222), (1234, 4321), (0, 999),
(99519000, 99519099)]:
fmt = '%%0%dd' % len(str(hi))
rx = regexp(lo, hi)
print('%4s - %-4s %s' % (fmt % lo, fmt % hi, rx))
m = re.compile('^%s$' % rx)
for i in range(0, 1+int(replace(str(hi), '9'))):
if m.match(fmt % i):
assert lo <= i <= hi, i
else:
assert i < lo or i > hi, i
la funzione regexp(lo, hi) costruisce un'espressione regolare che corrisponde valori tra 0.123.893,88762 milionie hi (zero riempito alla lunghezza massima). probabilmente è necessario inserire un ^ prima e un $ dopo (come nel codice di prova) per forzare la corrispondenza a essere l'intera stringa.
l'algoritmo è in realtà piuttosto semplice - divide ricorsivamente le cose in prefissi comuni e "blocchi completi". un blocco completo è qualcosa come 200-599 e può essere abbinato in modo affidabile (in questo caso con [2-5]\d{2}).
così 123-599 è diviso in 123-199 e 200-599. l'ultima metà è un blocco completo, la prima metà ha un prefisso comune di 1 e 23-99, che è ricorsivamente gestito come 23-29 (prefisso comune) e 30-99 (blocco completo) (e terminiamo alla fine, perché gli argomenti ad ogni chiamata sono più brevi dell'input iniziale).
l'unico dettaglio brutto è il prefix, che è necessario perché gli argomenti a regexp() sono numeri interi, così quando viene chiamato per generare, ad esempio, l'espressione regolare per 00-09 in realtà genera l'espressione regolare per 0-9, senza leader 0.
l'uscita è un gruppo di casi di test, che mostra la gamma e regexp:
0 - 0 0
0 - 1 [0-1]
0 - 2 [0-2]
0 - 9 \d
00 - 10 (0\d|10)
00 - 11 (0\d|1[0-1])
000 - 101 (0\d\d|10[0-1])
1 - 1 1
1 - 2 [1-2]
1 - 9 [1-9]
01 - 10 (0[1-9]|10)
01 - 11 (0[1-9]|1[0-1])
001 - 101 (0(0[1-9]|[1-9]\d)|10[0-1])
000 - 123 (0\d\d|1([0-1]\d|2[0-3]))
111 - 123 1(1[1-9]|2[0-3])
123 - 222 (1(2[3-9]|[3-9]\d)|2([0-1]\d|2[0-2]))
123 - 333 (1(2[3-9]|[3-9]\d)|2\d\d|3([0-2]\d|3[0-3]))
123 - 444 (1(2[3-9]|[3-9]\d)|[2-3]\d{2}|4([0-3]\d|4[0-4]))
000 - 321 ([0-2]\d{2}|3([0-1]\d|2[0-1]))
111 - 321 (1(1[1-9]|[2-9]\d)|2\d\d|3([0-1]\d|2[0-1]))
222 - 321 (2(2[2-9]|[3-9]\d)|3([0-1]\d|2[0-1]))
321 - 333 3(2[1-9]|3[0-3])
321 - 444 (3(2[1-9]|[3-9]\d)|4([0-3]\d|4[0-4]))
123 - 321 (1(2[3-9]|[3-9]\d)|2\d\d|3([0-1]\d|2[0-1]))
111 - 121 1(1[1-9]|2[0-1])
121 - 222 (1(2[1-9]|[3-9]\d)|2([0-1]\d|2[0-2]))
1234 - 4321 (1(2(3[4-9]|[4-9]\d)|[3-9]\d{2})|[2-3]\d{3}|4([0-2]\d{2}|3([0-1]\d|2[0-1])))
000 - 999 \d\d{2}
99519000 - 99519099 995190\d\d
ci vuole un po 'per eseguire l'ultima prova passanti sopra 99999999 numeri.
le espressioni devono essere sufficientemente compatte per evitare qualsiasi limite di buffer (direi che la dimensione della memoria peggiore è proporzionale al quadrato del numero di cifre nel numero più grande).
ps sto usando python 3, ma non credo che faccia molta differenza qui.
Perché non corrisponde il numero corretto di cifre ('\ d {8}'), e quindi per tutte le corrispondenze convertite in controllo int se è compreso nell'intervallo? – Scharron
addint a @rnbcoder ha scritto non puoi convertire str a int e confrontare? 'int (start_number) <= test_number <= (end_number)' –
C'è qualche ragione per fare una regex? Vorrei solo convertire il numero in un int e controllare se è tra start_number e end_number. Questo può essere leggermente meno efficiente, ma l'ordine di complessità è lo stesso, dal momento che il controllo di una corrispondenza regolare è O (n), e la conversione di string in int è O (n), quindi i due confronti int sono O (1). –