Javascript regex: Trova tutti gli URL ottimizzazione

Question

Questa domanda è un follow-up per il seguente post: Javascript regex: Find all URLs outside <a> tags - Nested Tags

ho scoperto che il codice:

\b((https?|ftps?):\/\/[^"<\s]+)(?![^<>]*>|[^"]*?<\/a) 

è estremamente inefficiente rispetto al eseguendolo separatamente per http e ftp parte in questo modo:

\b(https?:\/\/[^"<\s]+)(?![^<>]*>|[^"]*?<\/a) 

e

\b(ftps?:\/\/[^"<\s]+)(?![^<>]*>|[^"]*?<\/a) 

Ecco alcuni esempi in regex101.com:

• 1 ° metodo - 6395 steps
• secondo metodo - 3393 steps + 863 steps

Tuttavia, in uno dei miei pagina HTML questi codici confronta come gradini contro 7258 + 795 st eps, è abbastanza folle.

Per quanto ho visto, l'uso del modello (x|y) riduce la lunghezza di esecuzione ma qui probabilmente per una strana ragione è altrimenti.

Qualsiasi aiuto sarebbe apprezzato.

Answer 1

se si cerca di trovare tutti i collegamenti nel documento rispetto alla soluzione è questo. è restituire una matrice

document.anchors

Answer 2

Sembra che tu sei una vittima di catastrophic backtracking.

Questa espressione regolare fa il trucco in soli 3492 passi:

\b(?>(https?|ftps?):\/\/[^"<\s]+)(?![^<>]*>|[^"]*?<\/a) 

Tutto quello che ho fatto è stato fatto il primo gruppo un atomic group, causando il motore di scartare tutte le opzioni di backtracking una volta che è abbinato esso.

Questo è corretto nel tuo caso: puoi pensarci ora come due parti, "trova un URL" e poi "Usa il lookahead negativo per decidere se vogliamo tenerlo". La tua regex originale, una volta fallita l'analisi, procederà a tornare indietro nell'espressione di corrispondenza dell'URL. Il blocco [^"<\s]+ produrrebbe alcuni simboli, quindi proverebbe di nuovo il lookahead, quindi produrrà altri simboli e riproverà, e così via ...

Il motivo per cui l'aggiunta della parte https?|ftps? lo ha reso molto peggiore è stato che questo fornisce una fonte extra di backtracking (perdendo i s opzionali) in un modo che permetta a tutti i successivi backtracking di accadere di nuovo.

Sapete che regex101.com ha un'opzione "regex debugger" sulla barra degli strumenti a sinistra? Se lo usi, spiega in che modo la tua espressione regolare corrisponde a, quindi puoi (come ho appena fatto) capire dove si trova il pazzo backtracking.

Bonus Edit: Un ulteriore miglioramento uno che prende solo 3185 passi:

\b(?>ht|f)tps?:\/\/(?>[^"<\s]+)(?![^<>]+>|[^"]*?<\/a)