Performance issue with grep
I'm using grep to search for several regular expressions in a single file. In particular, I'm considering a 100 MB file with English subtitles and running the following regular expressions stored in file patterns.txt:
Cas.*eharden
acr.*otic
syn.*thesizing
sub.*abbot
iss.*acharite
bot.*onne
dis.*similatory
ove.*rmantel
isa.*tin
ado.*nijah
sol.*ution
zei.*st
fam.*ousness
inq.*uisitress
aor.*tography
via.*duct
ama.*sa
der.*ive
pie.*tas
kit.*chenette
While doing so I observed that the time required by grep does not grow linearly with the number of regular expressions. Indeed, it seems to grow exponentially.
Experiments
System: Intel(R) Core(TM) i5-5200U CPU @ 2.20GHz; 4 Cores; 8 GB RAM
Case 1: 20 regexps
Command grep -c -f patterns.txt subtitles.txt counts 2214 occurrences and takes
2,19s user 0,00s system 99% cpu 2,192 total.
Case 2: 30 regexps
If I add the following expressions to patterns.txt
ort.*hros
ove.*ridentify
mis.*tiest
pay.*ne
int.*erchasing
jej.*uneness
sta.*lactiform
und.*ertrain
cob.*bles
Sub.*category
Command grep -c -f patterns.txt subtitles.txt counts 2894 occurrences and takes 71,35s user 0,06s system 99% cpu 1:11,42 total.
Case 3: 35 regexps
Adding five more expressions:
dis.*embosom
imp.*ortunateness
ema.*thion
rho.*mb
haz.*elwood
Command grep -c -f patterns.txt subtitles.txt counts 2904 occurrences and takes 211,18s user 0,22s system 99% cpu 3:31,58 total
Why grep -f exhibit such behavior? What is it doing internally?
The whole set of regexp I've been using can be found here
From reading the grep source code, it appears that the regex's in your file are not executed one at a time. Rather, they're read all at once into one big regex:
case 'f':
fp = STREQ (optarg, "-") ? stdin : fopen (optarg, O_TEXT ? "rt" : "r");
if (!fp)
error (EXIT_TROUBLE, errno, "%s", optarg);
for (keyalloc = 1; keyalloc <= keycc + 1; keyalloc *= 2)
;
keys = xrealloc (keys, keyalloc);
oldcc = keycc;
while ((cc = fread (keys + keycc, 1, keyalloc - 1 - keycc, fp)) != 0)
{
keycc += cc;
if (keycc == keyalloc - 1)
keys = x2nrealloc (keys, &keyalloc, sizeof *keys);
}
This is confirmed watching an strace of grep run on your command:
open("testreg", O_RDONLY) = 3
fstat(3, {st_mode=S_IFREG|0664, st_size=124, ...}) = 0
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fd8912fe000
read(3, "ort.*hrosnove.*ridentifynmis.*ti"..., 4096) = 124
Backtracking regex implementations (which allow backreferences), do not run in O(n) time, but rather O(2^m), which can lead to catastrophic runtimes.
Your assumption that grep is simply looping over each regex in turn, compiling each into a DFA and then executing it is perfectly reasonable. However, it appears that the grep authors have assumed that by running your regex's all at once, they can probably do so more efficiently in some cases. The result is that by adding regex's to your file, you're falling into the O(2^m) runtime, resulting in an exponential increase in your runtime.
As it turns out, it may be more efficient to simply loop over each regex executing them one at a time, forcing your grep to run linearly. On my laptop, running grep version 2.20, I get the following results using only the last 29 regex's in the file you provided:
[Downloads]$ wc -l patterns.txt
29 patterns.txt
[Downloads]$ time grep -c -f ~/Downloads/patterns.txt /usr/share/dict/linux.words
117
real 0m3.092s
user 0m3.027s
sys 0m0.047s
[csd@alcazar Downloads]$ time for regex in `cat ~/Downloads/patterns.txt`; do grep -c $regex /usr/share/dict/linux.words > /dev/null; done
real 0m0.474s
user 0m0.312s
sys 0m0.158s
I'm a little late to this but want to try to clarify what the problem is.
First off, the .* should never span newlines, ever !!
Right out of the gate, you should never use separate regex that scan
the same target text territory (an entirely separate topic).
Ok, so at this point we are down to something doable.
We have a choice when constructing and combining regex's.
We can make each one a separate alternation for sure.
But, if we have a large number of mostly literal regexes, this will
cause problems.
Consider a regex trie consisting of mostly alphanumeric characters.
On the outer alternation level we only want to give the engine a maximum
of 26 pathways for the engine to traverse.
As we move to the secondary level (within each path) we want to give
the engine another 26 max pathways.
This choice happens again for those pathways, and each child pathway, etc...
This is the definition of a full blown, multi-level regex trie.
This greatly reduces the number of steps to a match, as I will show below.
I've taken your patterns.txt and made two types of expressions.
One without a trie, one with.
You have 580 separate patterns we will combine.
In the one without a trie, that makes 580 outer level pathways.
In the one with a trie, it makes 25 pathway.
Just that alone represents a 20 to 1 difference in speed.
Moving on, we go further and create all the sub-path trie's for each level.
This shaves another 10-30x in time doing this.
Your patterns are mostly uniform in that they each have a 3 letter constant
before the greedy quantifier .* .
After which, the sub-trie's are still constructed, but at this point are of
minor affect.
I've used the RegexFormat 8 utility called
Strings to Regex - Ternary Tree which generates full blown trie's
from string literals.
I am comparing this generated regex to the unaltered pattern list
regexes, in which I combined by added an alternation between each regex.
For the test sample, I used half of your
100 MB file with English subtitles
which was about 50 MB.
The test was conducted with the RegexFormat 8, built-in Benchmark Utility.
Regex1 is the full-blown generated trie.
Regex2 is non-trie version.
Each regex matched 36,776 items in the 50MB target.
The times however, are quite different.
Results:
Regex1: (?:A(?:gr.*iology|nk.*let|tt.*ributive)|Bow.*ls|Cas.*eharden|Iso.*propyl|L(?:ab.*ella|ic.*htenberg)|Neu.*stic|Oro.*nasally|Pen.*stemon|R(?:e(?:i.*nspiration|p.*rovable)|up.*ee)|S(?:hi.*gellae|te.*rlet|ub.*(?:category|epithelial))|Vit.*alian|Wer.*e|a(?:c(?:a.*demic|e.*t(?:aldol|ylation)|h.*enial|i.*dimeter|r.*otic)|d(?:e.*nosarcomata|m.*easurer|o.*nijah)|ec.*ium|ir.*less|l(?:e.*xandroupolis|k.*alisation|l.*owable|m.*swomen)|m(?:a.*sa|n.*esic|y.*xorrhea)|n(?:c.*one|e.*mogram|g.*elical|o.*(?:ciassociation|le)|t.*imechanistic)|or.*tography|p(?:i.*sh|o.*carpous|ï.*¿¥ï¾½ritif)|r(?:c.*hipelagic|m.*ored|n.*oldson|y.*balloid)|s(?:c.*endent|t.*ound)|tt.*ainder|u(?:d.*ience|s.*tralioid|t.*ostoper)|va.*re|zi.*muthal)|b(?:a(?:b.*ette|l.*let|n.*galay|r.*(?:a|racuda|tolozzi))|e(?:a.*dsman|r.*(?:dache|nardsville))|is.*ymmetrically|la.*ckbuck|o(?:b.*owler|g.*(?:hazk￥ﾡy|omilism)|o.*mingly|r.*onic|t.*onne|u.*rbonnais)|r(?:i.*olette|o.*(?:minate|wne)|y.*ophytic)|ui.*ldup)|c(?:a(?:j.*ole|r.*teret|s.*sie|t.*(?:awba|hexes))|e(?:n.*(?:serless|tralist)|r.*(?:emoniously|tify))|h(?:a.*nduy|l.*orohydrin|o.*ya|r.*omoplast)|li.*(?:ckless|ntonville|toridean)|o(?:b.*bles|c.*kaded|g.*itable|h.*esiveness|l.*(?:lectivise|onially|umba)|n.*(?:gregativeness|strictive|tortion|vulsive)|r.*deliers|ï.*¿¥ï¾¡peratively)|r(?:a.*ckers|c.*hes|e.*stline|o.*(?:akier|uton))|u(?:l.*turist|r.*bless)|ï¿.*¥ï¾½dula)|d(?:''.*s|a(?:m.*selfishes|n.*dier)|e(?:a.*minize|f.*enseless|h.*umanize|m.*ulsifying|r.*(?:ive|mabrasion)|s.*(?:de|iderative)|v.*(?:a|olatilizing))|i(?:a.*dochy|h.*ydromorphinone|p.*lomatical|s.*(?:e(?:mbosom|nfranchisement|stablish)|similatory|tinguished|yllabize)|v.*ulgement)|o(?:l.*phinfishes|o.*rstep|r.*ter)|r(?:a.*(?:gonhead|maturge)|e.*ssing|u.*dging)|ul.*cimer)|e(?:as.*iness|co.*nometrician|ff.*ortful|l(?:e.*git|o.*ign)|m(?:a.*thion|e.*ndatory)|pi.*zoite|qu.*ipoise|st.*afette|th.*(?:nolinguistics|yl(?:ated|dichloroarsine))|x(?:c.*uss|h.*umed|p.*(?:andible|iable|ostulation)|t.*ravasating)|yc.*k)|f(?:a(?:m.*ousness|n.*tasied)|e(?:l.*ony|r.*(?:rotype|vidly)|w.*er)|i(?:l.*ial|s.*her)|l(?:a.*m(?:b￥ﾽ|eproof)|e.*et)|o(?:r.*(?:dyce|mularize)|z.*iness)|re.*ak|u(?:n.*goid|r.*ry))|g(?:a(?:l.*(?:act(?:in|oid)|vanically|way)|s.*(?:ifier|trostomy)|u.*(?:l|ssmeter))|e(?:g.*enion|n.*(?:eseo|ista)|o.*phyte|s.*tative)|in.*gili|lo.*(?:be|ssary)|o(?:d.*(?:hood|liest)|l.*dberg)|r(?:a.*(?:n(?:ddaddy|ulating)|vimetry)|e.*endale)|ua.*iacum|wy.*dion)|h(?:a(?:l.*lmark|r.*d(?:handed|ly)|s.*tefully|t.*shepset|z.*elwood)|e(?:a.*rt(?:eningly|sick)|c.*tometre|m.*atoid|p.*tode|t.*erodactyl|u.*neburg)|id.*eout|o(?:n.*orius|p.*s|r.*(?:nbeam|ribly)|v.*elled)|u(?:n.*k|r.*ricane)|y(?:o.*scine|p.*othallus))|i(?:d(?:e.*ler|m.*on)|ll.*iquidly|m(?:m.*obilize|p.*(?:ort(?:antly|unateness)|udently))|n(?:a.*dequacy|c.*linable|d.*ustrialised|e.*quitable|f.*ringer|g.*rate|q.*uisitress|t.*(?:er(?:aural|belligerent|chasing|hybridized|mundane)|ranuclear))|od.*ise|r(?:e.*nical|k.*someness|r.*uptively)|s(?:a.*tin|s.*acharite))|j(?:a(?:i.*na|m.*aican)|e(?:a.*n|d.*burgh|j.*uneness|w.*ishness)|id.*da|ud.*ea)|k(?:am.*seen|ea.*nsburg|i(?:l.*obaud|t.*chenette)|la.*nism|on.*a|uw.*ait)|l(?:ac.*unaria|i(?:e.*der|m.*acine|n.*us|q.*uer|s.*tlessly)|o(?:c.*k|g.*(?:iciz(?:e|ing)|ographer))|u(?:k.*s|m.*inal)|ym.*phogranulomata)|m(?:a(?:m.*al(?:lapuram|uke)|r.*(?:acanda|or)|s.*sys)|ca.*llen|e(?:i.*lhac|t.*hylate)|i(?:n.*imalist|s.*(?:a(?:nalyzing|uthorizing)|ce|quoting|shipping|tiest)|t.*tatur)|on.*othelitic|u(?:l.*ti(?:chrome|volumed)|s.*siest))|n(?:at.*atoriums|e(?:c.*rologically|m.*o|o.*styled|p.*hritic|t.*tlelike|u.*roglial|w.*fangledly)|o(?:g.*gin|n.*(?:a(?:mendment|scetic|ttachment)|dilution|knowledgeable|narrative|receptive|s(?:a(?:cramental|linity)|ecrecy|tability|uspended))|r.*mandy|u.*akchott)|ur.*turable)|o(?:li.*o|p(?:e.*nairness|h.*thalmoscopy|s.*onin)|r(?:a.*cles|i.*entally|o.*logist|t.*hros)|sc.*illator|u(?:s.*el|t.*(?:chasing|drew|echoing))|ve.*r(?:glad|hang|i(?:dentify|mpressibility|ntensified)|m(?:antel|uch)|spacious|thriftiness)|wl.*ishness|xy.*genicity)|p(?:a(?:r.*(?:a(?:professional|tences)|entalia)|y.*ne)|e(?:d.*al|e.*p|n.*(?:etrableness|u(?:mbra|rious))|r.*(?:ches|istaltically))|h(?:i.*landerer|o.*(?:nautograph|to(?:n|static)))|i(?:c.*nicking|e.*tas|n.*gr|p.*pin)|la.*yday|ne.*umoencephalogram|o(?:o.*fter|p.*sy)|r(?:e.*(?:a(?:cceptance|ffiliated|ging)|con(?:flict|triving)|d(?:eprive|is(?:ciplined|guise))|expeditionary|historically|insult|judger|pense|s(?:entimental|u(?:bscription|itable))|t(?:ry|ypify))|o.*(?:fligateness|mulger|t(?:eid|oplasmic)))|se.*udo(?:cele|nymous)|u(?:b.*licized|i.*rness|n.*ctualness|r.*sing|t.*rilaginous)|yx.*is)|qu(?:a.*rreler|i.*st|o.*dlibetically)|r(?:a(?:d.*iotelemetry|g.*gedy)|e(?:c.*(?:ampaign|umbent)|d.*ominating|e.*xpose|f.*ulgentness|i.*(?:maged|nhardt|temized)|m.*ontoire|o.*rientating|p.*(?:e(?:llant|n)|lunging)|s.*hook|t.*(?:elegraph|ral)|v.*ocableness)|h(?:i.*naria|o.*mb)|i(?:d.*dle|f.*leman)|o(?:d.*eo|l.*lo|u.*che|y.*ce))|s(?:a(?:l.*ic|n.*(?:ctimonious|d))|c(?:e.*ptic|o.*ttish|r.*u(?:ffiest|mpy)|u.*lptor)|e(?:l.*ves|p.*arator)|h(?:e.*lbyville|i.*pboard|o.*shone)|in.*(?:cerely|gularise)|lo.*wpoke|m(?:i.*dgin|o.*keproof)|o(?:l.*ution|p.*rano|r.*(?:bian|rento)|u.*thwest)|p(?:a.*lato|i.*nning|r.*itehood)|t(?:a.*(?:lactiform|minodia|ndish|toblast)|e.*rope|i.*lyaga)|u(?:b.*(?:abbot|extensible|foliation|jectional|preceptorial|stantialness|tegumental)|k.*arnapura|l.*liable|n.*ward|p.*eracquisition)|wi.*m|yn.*thesizing)|t(?:a(?:l.*kie|t.*tooed)|e(?:l.*e(?:cast|g|ran)|n.*sionless|r.*minatory|t.*radrachm)|h(?:e.*(?:ban|r(?:m(?:alize|obarograph)|ophyte)|spian)|i.*osinamine)|ig.*r￥ﾽ|o(?:n.*eless|r.*ulosis)|ra.*(?:lles|pani)|u(?:m.*idity|n.*eableness)|w(?:e.*enies|o.*three)|y(?:l.*er|p.*ewrote))|u(?:lt.*raviruses|n(?:b.*(?:esmirched|oring)|c.*o(?:mmitted|n(?:fronted|tr(?:asted|ibutory)))|d.*(?:e(?:based|r(?:framework|nourish|populated|train))|ischarged|rowned)|e.*xceeded|f.*orgeability|g.*(?:oaded|roupable)|l.*oyalty|m.*ounting|o.*ceanic|p.*(?:erishing|hlegmatic|recocious)|r.*e(?:ached|counted|solvable)|s.*(?:e(?:parative|rrate)|hadowable|ilicified|l(?:immed|uiced)|naky|pelt|t(?:ealthy|oppably)|werving)|t.*(?:heistical|r(?:ansparent|ustworthy))|u.*seful|w.*hisked)|p(?:b.*ear|p.*ercutting)|rs.*ula)|v(?:a(?:l.*ois|p.*orize|r.*as|t.*ican)|er.*us|i(?:a.*duct|c.*tualing|l.*lose)|ul.*canizer)|w(?:a(?:r.*rington|x.*y)|e(?:a.*rability|s.*termarck)|he.*rrit|i(?:s.*teria|t.*hy)|ul.*fenite)|y(?:es.*enin|ol.*ande)|z(?:e(?:b.*ec|i.*st|l.*os)|on.*ule))
Options: < none >
Completed iterations: 1 / 1 ( x 1 )
Matches found per iteration: 36776
Elapsed Time: 19.94 s, 19936.96 ms, 19936963 µs
Regex2: (?:Cas.*eharden|acr.*otic|... (truncated)
Options: < none >
Completed iterations: 1 / 1 ( x 1 )
Matches found per iteration: 36776
Elapsed Time: 299.74 s, 299735.86 ms, 299735857 µs
The regex is better seen when formatted (expanded).
Conclusion - I recommend using a full blown trie which will cure your
latency problem's.
Good luck !!
If you have any questions, feel free to ask.
(?:
A
(?:
gr .* iology
| nk .* let
| tt .* ributive
)
| Bow .* ls
| Cas .* eharden
| Iso .* propyl
| L
(?: ab .* ella | ic .* htenberg )
| Neu .* stic
| Oro .* nasally
| Pen .* stemon
| R
(?:
e
(?: i .* nspiration | p .* rovable )
| up .* ee
)
| S
(?:
hi .* gellae
| te .* rlet
| ub .*
(?: category | epithelial )
)
| Vit .* alian
| Wer .* e
| a
(?:
c
(?:
a .* demic
| e .* t
(?: aldol | ylation )
| h .* enial
| i .* dimeter
| r .* otic
)
| d
(?:
e .* nosarcomata
| m .* easurer
| o .* nijah
)
| ec .* ium
| ir .* less
| l
(?:
e .* xandroupolis
| k .* alisation
| l .* owable
| m .* swomen
)
| m
(?: a .* sa | n .* esic | y .* xorrhea )
| n
(?:
c .* one
| e .* mogram
| g .* elical
| o .*
(?: ciassociation | le )
| t .* imechanistic
)
| or .* tography
| p
(?:
i .* sh
| o .* carpous
| ï .* ¿¥ï¾½ritif
)
| r
(?:
c .* hipelagic
| m .* ored
| n .* oldson
| y .* balloid
)
| s
(?: c .* endent | t .* ound )
| tt .* ainder
| u
(?:
d .* ience
| s .* tralioid
| t .* ostoper
)
| va .* re
| zi .* muthal
)
| b
(?:
a
(?:
b .* ette
| l .* let
| n .* galay
| r .*
(?: a | racuda | tolozzi )
)
| e
(?:
a .* dsman
| r .*
(?: dache | nardsville )
)
| is .* ymmetrically
| la .* ckbuck
| o
(?:
b .* owler
| g .*
(?: hazk￥ﾡy | omilism )
| o .* mingly
| r .* onic
| t .* onne
| u .* rbonnais
)
| r
(?:
i .* olette
| o .*
(?: minate | wne )
| y .* ophytic
)
| ui .* ldup
)
| c
(?:
a
(?:
j .* ole
| r .* teret
| s .* sie
| t .*
(?: awba | hexes )
)
| e
(?:
n .*
(?: serless | tralist )
| r .*
(?: emoniously | tify )
)
| h
(?:
a .* nduy
| l .* orohydrin
| o .* ya
| r .* omoplast
)
| li .*
(?: ckless | ntonville | toridean )
| o
(?:
b .* bles
| c .* kaded
| g .* itable
| h .* esiveness
| l .*
(?: lectivise | onially | umba )
| n .*
(?:
gregativeness
| strictive
| tortion
| vulsive
)
| r .* deliers
| ï .* ¿¥ï¾¡peratively
)
| r
(?:
a .* ckers
| c .* hes
| e .* stline
| o .*
(?: akier | uton )
)
| u
(?: l .* turist | r .* bless )
| ï¿ .* ¥ï¾½dula
)
| d
(?:
'' .* s
| a
(?: m .* selfishes | n .* dier )
| e
(?:
a .* minize
| f .* enseless
| h .* umanize
| m .* ulsifying
| r .*
(?: ive | mabrasion )
| s .*
(?: de | iderative )
| v .*
(?: a | olatilizing )
)
| i
(?:
a .* dochy
| h .* ydromorphinone
| p .* lomatical
| s .*
(?:
e
(?: mbosom | nfranchisement | stablish )
| similatory
| tinguished
| yllabize
)
| v .* ulgement
)
| o
(?:
l .* phinfishes
| o .* rstep
| r .* ter
)
| r
(?:
a .*
(?: gonhead | maturge )
| e .* ssing
| u .* dging
)
| ul .* cimer
)
| e
(?:
as .* iness
| co .* nometrician
| ff .* ortful
| l
(?: e .* git | o .* ign )
| m
(?: a .* thion | e .* ndatory )
| pi .* zoite
| qu .* ipoise
| st .* afette
| th .*
(?:
nolinguistics
| yl
(?: ated | dichloroarsine )
)
| x
(?:
c .* uss
| h .* umed
| p .*
(?: andible | iable | ostulation )
| t .* ravasating
)
| yc .* k
)
| f
(?:
a
(?: m .* ousness | n .* tasied )
| e
(?:
l .* ony
| r .*
(?: rotype | vidly )
| w .* er
)
| i
(?: l .* ial | s .* her )
| l
(?:
a .* m
(?: b￥ﾽ | eproof )
| e .* et
)
| o
(?:
r .*
(?: dyce | mularize )
| z .* iness
)
| re .* ak
| u
(?: n .* goid | r .* ry )
)
| g
(?:
a
(?:
l .*
(?:
act
(?: in | oid )
| vanically
| way
)
| s .*
(?: ifier | trostomy )
| u .*
(?: l | ssmeter )
)
| e
(?:
g .* enion
| n .*
(?: eseo | ista )
| o .* phyte
| s .* tative
)
| in .* gili
| lo .*
(?: be | ssary )
| o
(?:
d .*
(?: hood | liest )
| l .* dberg
)
| r
(?:
a .*
(?:
n
(?: ddaddy | ulating )
| vimetry
)
| e .* endale
)
| ua .* iacum
| wy .* dion
)
| h
(?:
a
(?:
l .* lmark
| r .* d
(?: handed | ly )
| s .* tefully
| t .* shepset
| z .* elwood
)
| e
(?:
a .* rt
(?: eningly | sick )
| c .* tometre
| m .* atoid
| p .* tode
| t .* erodactyl
| u .* neburg
)
| id .* eout
| o
(?:
n .* orius
| p .* s
| r .*
(?: nbeam | ribly )
| v .* elled
)
| u
(?: n .* k | r .* ricane )
| y
(?: o .* scine | p .* othallus )
)
| i
(?:
d
(?: e .* ler | m .* on )
| ll .* iquidly
| m
(?:
m .* obilize
| p .*
(?:
ort
(?: antly | unateness )
| udently
)
)
| n
(?:
a .* dequacy
| c .* linable
| d .* ustrialised
| e .* quitable
| f .* ringer
| g .* rate
| q .* uisitress
| t .*
(?:
er
(?:
aural
| belligerent
| chasing
| hybridized
| mundane
)
| ranuclear
)
)
| od .* ise
| r
(?:
e .* nical
| k .* someness
| r .* uptively
)
| s
(?: a .* tin | s .* acharite )
)
| j
(?:
a
(?: i .* na | m .* aican )
| e
(?:
a .* n
| d .* burgh
| j .* uneness
| w .* ishness
)
| id .* da
| ud .* ea
)
| k
(?:
am .* seen
| ea .* nsburg
| i
(?: l .* obaud | t .* chenette )
| la .* nism
| on .* a
| uw .* ait
)
| l
(?:
ac .* unaria
| i
(?:
e .* der
| m .* acine
| n .* us
| q .* uer
| s .* tlessly
)
| o
(?:
c .* k
| g .*
(?:
iciz
(?: e | ing )
| ographer
)
)
| u
(?: k .* s | m .* inal )
| ym .* phogranulomata
)
| m
(?:
a
(?:
m .* al
(?: lapuram | uke )
| r .*
(?: acanda | or )
| s .* sys
)
| ca .* llen
| e
(?: i .* lhac | t .* hylate )
| i
(?:
n .* imalist
| s .*
(?:
a
(?: nalyzing | uthorizing )
| ce
| quoting
| shipping
| tiest
)
| t .* tatur
)
| on .* othelitic
| u
(?:
l .* ti
(?: chrome | volumed )
| s .* siest
)
)
| n
(?:
at .* atoriums
| e
(?:
c .* rologically
| m .* o
| o .* styled
| p .* hritic
| t .* tlelike
| u .* roglial
| w .* fangledly
)
| o
(?:
g .* gin
| n .*
(?:
a
(?: mendment | scetic | ttachment )
| dilution
| knowledgeable
| narrative
| receptive
| s
(?:
a
(?: cramental | linity )
| ecrecy
| tability
| uspended
)
)
| r .* mandy
| u .* akchott
)
| ur .* turable
)
| o
(?:
li .* o
| p
(?:
e .* nairness
| h .* thalmoscopy
| s .* onin
)
| r
(?:
a .* cles
| i .* entally
| o .* logist
| t .* hros
)
| sc .* illator
| u
(?:
s .* el
| t .*
(?: chasing | drew | echoing )
)
| ve .* r
(?:
glad
| hang
| i
(?: dentify | mpressibility | ntensified )
| m
(?: antel | uch )
| spacious
| thriftiness
)
| wl .* ishness
| xy .* genicity
)
| p
(?:
a
(?:
r .*
(?:
a
(?: professional | tences )
| entalia
)
| y .* ne
)
| e
(?:
d .* al
| e .* p
| n .*
(?:
etrableness
| u
(?: mbra | rious )
)
| r .*
(?: ches | istaltically )
)
| h
(?:
i .* landerer
| o .*
(?:
nautograph
| to
(?: n | static )
)
)
| i
(?:
c .* nicking
| e .* tas
| n .* gr
| p .* pin
)
| la .* yday
| ne .* umoencephalogram
| o
(?: o .* fter | p .* sy )
| r
(?:
e .*
(?:
a
(?: cceptance | ffiliated | ging )
| con
(?: flict | triving )
| d
(?:
eprive
| is
(?: ciplined | guise )
)
| expeditionary
| historically
| insult
| judger
| pense
| s
(?:
entimental
| u
(?: bscription | itable )
)
| t
(?: ry | ypify )
)
| o .*
(?:
fligateness
| mulger
| t
(?: eid | oplasmic )
)
)
| se .* udo
(?: cele | nymous )
| u
(?:
b .* licized
| i .* rness
| n .* ctualness
| r .* sing
| t .* rilaginous
)
| yx .* is
)
| qu
(?:
a .* rreler
| i .* st
| o .* dlibetically
)
| r
(?:
a
(?: d .* iotelemetry | g .* gedy )
| e
(?:
c .*
(?: ampaign | umbent )
| d .* ominating
| e .* xpose
| f .* ulgentness
| i .*
(?: maged | nhardt | temized )
| m .* ontoire
| o .* rientating
| p .*
(?:
e
(?: llant | n )
| lunging
)
| s .* hook
| t .*
(?: elegraph | ral )
| v .* ocableness
)
| h
(?: i .* naria | o .* mb )
| i
(?: d .* dle | f .* leman )
| o
(?:
d .* eo
| l .* lo
| u .* che
| y .* ce
)
)
| s
(?:
a
(?:
l .* ic
| n .*
(?: ctimonious | d )
)
| c
(?:
e .* ptic
| o .* ttish
| r .* u
(?: ffiest | mpy )
| u .* lptor
)
| e
(?: l .* ves | p .* arator )
| h
(?:
e .* lbyville
| i .* pboard
| o .* shone
)
| in .*
(?: cerely | gularise )
| lo .* wpoke
| m
(?: i .* dgin | o .* keproof )
| o
(?:
l .* ution
| p .* rano
| r .*
(?: bian | rento )
| u .* thwest
)
| p
(?: a .* lato | i .* nning | r .* itehood )
| t
(?:
a .*
(?: lactiform | minodia | ndish | toblast )
| e .* rope
| i .* lyaga
)
| u
(?:
b .*
(?:
abbot
| extensible
| foliation
| jectional
| preceptorial
| stantialness
| tegumental
)
| k .* arnapura
| l .* liable
| n .* ward
| p .* eracquisition
)
| wi .* m
| yn .* thesizing
)
| t
(?:
a
(?: l .* kie | t .* tooed )
| e
(?:
l .* e
(?: cast | g | ran )
| n .* sionless
| r .* minatory
| t .* radrachm
)
| h
(?:
e .*
(?:
ban
| r
(?:
m
(?: alize | obarograph )
| ophyte
)
| spian
)
| i .* osinamine
)
| ig .* r￥ﾽ
| o
(?: n .* eless | r .* ulosis )
| ra .*
(?: lles | pani )
| u
(?: m .* idity | n .* eableness )
| w
(?: e .* enies | o .* three )
| y
(?: l .* er | p .* ewrote )
)
| u
(?:
lt .* raviruses
| n
(?:
b .*
(?: esmirched | oring )
| c .* o
(?:
mmitted
| n
(?:
fronted
| tr
(?: asted | ibutory )
)
)
| d .*
(?:
e
(?:
based
| r
(?:
framework
| nourish
| populated
| train
)
)
| ischarged
| rowned
)
| e .* xceeded
| f .* orgeability
| g .*
(?: oaded | roupable )
| l .* oyalty
| m .* ounting
| o .* ceanic
| p .*
(?: erishing | hlegmatic | recocious )
| r .* e
(?: ached | counted | solvable )
| s .*
(?:
e
(?: parative | rrate )
| hadowable
| ilicified
| l
(?: immed | uiced )
| naky
| pelt
| t
(?: ealthy | oppably )
| werving
)
| t .*
(?:
heistical
| r
(?: ansparent | ustworthy )
)
| u .* seful
| w .* hisked
)
| p
(?: b .* ear | p .* ercutting )
| rs .* ula
)
| v
(?:
a
(?:
l .* ois
| p .* orize
| r .* as
| t .* ican
)
| er .* us
| i
(?: a .* duct | c .* tualing | l .* lose )
| ul .* canizer
)
| w
(?:
a
(?: r .* rington | x .* y )
| e
(?: a .* rability | s .* termarck )
| he .* rrit
| i
(?: s .* teria | t .* hy )
| ul .* fenite
)
| y
(?: es .* enin | ol .* ande )
| z
(?:
e
(?: b .* ec | i .* st | l .* os )
| on .* ule
)
)
上一篇: 为外部库编写JavaDocs
下一篇: 性能问题与grep