Logo TIB AV-Portal Logo TIB AV-Portal

Index support for regular expression search

Video in TIB AV-Portal: Index support for regular expression search

Formal Metadata

Index support for regular expression search
Title of Series
Number of Parts
CC Attribution - NonCommercial - ShareAlike 3.0 Unported:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this license.
Release Date

Content Metadata

Subject Area
Regular expressions (regex) are powerful tool for text processing. When dealing with large string collections it's important to search fast on that collections (i.e. search using index). Indexing for regex search is a quite hard task. This talk presents novel technique (and WIP patch for PostgreSQL implementing it) for regex search using trigram indexes. Proposed technique provides more comprehensive trigram extraction than analogues, i.e. higher performance. There are two existed approaches for index-based regex search. The FREE indexing engine is based on extractions continued text fractions from regex and perform substring search. Google Code Search approach present more sophisticated recursive analysis of regex with extraction of various regex attributes. This talk presents novel technique of regex analysis which is based on automata transformation rather than original regex analysis. Superiority of proposed technique will be proved by examples and tests. The talk would be organized as following: Introduction. Regular expressions Finite automata pg trgm contrib module Existing techniques for index-based regular expression search FREE indexing engine Google Code Search Proposed technique Description Examples Comparison with analogues Limitations Performance results.
man ordinal First-Order Regular Expressions several theoretical connections degree proof Computer animation speech Reg Video tasks
Regular Expressions states Graph time sets Automata area information ease of use processes Reg vertices model Arc formal classes data types Graph relation formating real states theoretical Transformers Regular Expressions sequence system call information infinite processes Computer animation string classes Arc
domain rules states time web pages moment sets loss Regular Expressions sequence number wave sign processes radiation phase Self-reference law model spacetime Arc
CAN-bus processes Tower share Regular Expressions optimal sequence
implementation Sichtbarkeiten code unit similar loss distances signatures number inverse problems Void's Indexable structure model implementation focus exponents breadth Regular Expressions measures words logic string Right metrics tasks inverted Results
Actions Regular Expressions link Open Source Ranges help student information period different Em's model position systems hard Graph information The list Databases lines specific period Drums case formal selection organization pattern table progress Results
unit Commodore Emulation
Ordinary Differential Equations Regular Expressions fraction Explorative Datenanalyse ses means graphical user interface Computer animation logic case orders diagrams table position
hard Regular Expressions states Quantifier part variables fraction evaluation inverse problems topology different case Indexable Query Reg form states Continuous Regular Expressions fraction case string optics simulation Vacuum
Super Open Source time unit sources expansions rules elements Google operations vertices series continuous rules moment share code staff Continuous Regular Expressions several CAN-bus means fraction logic string sum source
statistics Regular Expressions closed necessities sets part rules fields Pointer goods evaluation inverse problems Google Indexable Query descriptions relation characteristics Gender closed code coma Regular Expressions similar category means Google Computer animation Query case
category message-based Transformers Google code hill Stream Regular Expressions sum reading
Trigonometrie Graph Transformers Graph administrations corresponds graphs analysis Transformers Regular Expressions part Automata theoretical message-based Indexable box sum inverted kernel
states necessities sources part number ease of use Pointer diagrams model PEAS God man Graph key Prisoner's Dilemma moment Transformers Regular Expressions category message-based processes Computer animation Self-reference formal life sum band progress Results spacetime WAN
addition comparison states Menu lines Transformers Regular Expressions Semantics fraction Explorative Datenanalyse message-based angles hypermedia different logic single table comparison matrix form
man unit Sichtbarkeiten integrators time Robots breadth experts fit Databases scans Regular Expressions Kettenbruch strategy different life Right sum figure Free comparison sum localization form
presentation Actions states Graph lines time deterministically loss water The list infinity Automata Coloured automatische Ableitung graphical user interface different Rolling box Representation model multiple stable tasks presentation shift Graph information patched graphs share lines Regular Expressions Berechnungskomplexität Terminal processes case string orders life state machines progress since Arc Vacuum kernel
NET projects effects Menu help 3rd area number means case string Video life diagrams game tasks position tasks
implementation statistics Actions mud Databases part dimension inference goods different Void's law integer diagrams comparison sum Security optimal position classes area user interfaces addition Elektronischer Datenaustausch information breadth scans Regular Expressions sequence alternatives logic Query case input sum
flow bottom functionality link studies part rules powerful memory operations negative Rolling level model comparison position classes scale information moment Content lines Transformers Regular Expressions measures means table matrix reading Results
OK let's start so my name is Alexander Koyré proof my talk is My my talk is about and for ordinal expressed search so you can refer the problem when you do need to search using regular expressions on large collections there was little approaches to accelerated good news so you can just do some more some faster that much of the expression Or you can do much in full for each thing in collection by using an English More than that degree expression engines are already well optimise it and also do fast emergent don't let you avoid old old collections and then index separates for ordinal expression of search users really and when you need to do such search on lasting connection At 1st I would like to do a gentle introduction in the regular expression because almost all the fast but no single expressions know how to write them and use them in a practical tasks but not all of us know underlying theory but is a serious in some net minumum will use required to understand my speech
So really all known as integral expression this powerful tool for text processing must not all of us know that it's based on formal language now in and therefore formal and Syrian introduce notion of language language is the set of stinks possible infinite set of things And also this serious sees uh that's it'll expressions are expressing same class of languages as the need of the matter On Is this means that we can transform the dual expression both in what the model and the is that article expression that would have the same set of matching extends as corresponding the need for the model Moreover the assassins formation is not only a wearable was serious about it its is actually used by medical expression vengeance So let the talk about what what the modern ease at the model is a graph of each of the reactants is a call its states and the arcs are labeled by charters of seeing and say that outer Martinetti's being the frequent itemsets think by some relation between states from special state called the initial state to some other special state called final state will consider some examples refer as such simple political expression we should leave things which can't be attracted a then sequence of challenges BC which can be repeated any amount of time possibly 0 amount of time and then Richardson the
Is this article expression will be transformed to fall and what the model is a set amount of initial state is marked by and for final state is marked by marked by a number sign So the initial state forever so it finds an arc of each much and to any charges it means that we can start Stewart was this but it'll expression much in you know any or and or stink so we never lose as this initial state as and we can reject it and the candidate any amount of sequences BC by some additional to upper states and back and then we can in the and is the final state final state also have some reference and are it means that wants to read Each final state we'll never miss it is that means that if we find much it doesn't matter what It after after a while you have the new wave of matching with questions please do it in this I was then knowledge of of that state is activated so that the state was effective is in this space becomes x if ever if the next chapter is not the name of this space is is but initial state remains active during whole process of matching so sold in the in the moment of time could be x if any states from 0 to all states obtained like expecially if if Loss state is that if we can stop because if no stable if it's if it's really means until the end of this thing can be at most was it to you you know what each the final state I will consider some example probably the treelet clarify this thing For example we fear assessment and initially initial state is In Is that of challenge It's And then all of the states is that the way only initial state is because the church it is not a self-reference art work and the initial state the main at Of the same situation is repeated until you need chunks of the land started running reminiscent in them it activates a state in the middle Initial state domain X if it really main active duty in all my process because it felt so reference in art which much in each Then The 1st of fine charts billions and upper state is Actually and so on Of Zambia each final state and this state of you will remain at front you end of the thing and you and radiation those the inca and final state is if refinish much processing you can say is that I think there is much and to regular expression
Now also beginning the 1st actually used because the 3rd phase a self-referencing Park
About the guy shows this process resulting optimization Share So know all of us most often compelled to go into this actually is this picture is not related here and because these guys are starting expression this doesn't mean uh Chino online and serious about any resistance from a k now about regular expression based search in that the base it's a good music but if you can do little expression business search and while it's only and it's a question of sky this is the bad news
All the different goes to do integral expression based index search users based on inverted indexes on q-grams I would like to do a gentle introduction into words in the appendix is soft you
To go is a substring qualified regional things we show our lands you it it can be used as a measure of what is nothing what does it mean to be measure for his most thing it means is that you can say some simple credible about results in lowering of this thing by only a narrow and was that some due grounds present existing and some q-grams not present in thing and Z. Q. granted focus is widely used in right in the reduced stink persistent past not expression watching for example and also the use of the you know it it distance searching can actually in distance insertion and also number of much you grants can be used as there are also some metrics off steam similarity delight in unit the G. D. RGM candidate model But that in the exponent you guns maintain cessation between you grammar and that all of those things where these uh you present so EGG argentaffin is an implementation for some particular q 4 q equal to the little example code of logical structure of the Jedi index it's not physical such a physical structures is much more complicated just logical structure for each you you can find the number of stinks where the skew around as
Something about students I dugongs favor different frequencies in existing so for example the the the papers titles reach among these 2 . 5 newtons contains some with Romania battles spent painted on the grounds that it is the most common thing on the English language The But you free of find if you'd like to find titles each contained guns ZZZ there is only 1 of battle company that the ground so all of this battle and get my and interest and I the presence information about the probably also interested in but what is there was only 1 battle campaigns that serves So not all the grounds of its if you are equally useful for example you you probably don't like to get the Boston is the list of the where the grammars there is present because it's so it it is a very large probably you can do a better results that gets in says she's probably would produce more false positive but it anyway we'll be Greek To avoid the this minuses offset the grounds of pizza Q can be used radio links systems so called the drums all multigrams This means that each you ground can specific you solve that make the city city of all q gons similar so we can do as ductility offers them equal but we can do is you might have to be in some model with a wide range of for example if some of the graph is weighted frequent we're going a use of forward answer in such cases and if some of the ground is me probably would like to group assessed the guns into the ground and this would lead to more effective and the church But that are some problems people get this in the because when Some paper describes differences of the guns of multigrams as a primary describe it like we have some fixes the collection and once we collect frequencies and doing that is they don't describe how we can maintain them line because in progress and can see user if you think this you can you can ensure updated deleted table it's unreasonable this is the 1st problem is this problem is avoidable but that is also the 2nd problem 2nd problem is patterns but in pattern but also how I can because only need a score of papers to corresponding but insufficient provisions to implement this in open source database probably this probably it is avoidable because we can use some of and other organizations but I don't know I'm not alone and I don't know if this but car is a classical idea the guns and that is not that is not the way to avoid the spot so I will post this question to be g advocacy and probably is a little further help to solve this problem
So what's the problem with the way the world be it this so is still a 10 year it happened that have been used for for years you know and and so we can discuss this later
The way it's all about we the This And the next question is how to use such indexes for regular expression search
General ideas so that when we have some general expression we can derive at some a logical expression which express their wish diagrams should be present in distinct in order to existing can be much Stuart it'll expression as this uh and doesn't doesn't mean that you should not this city might be a little some of false positives bot don't alone False negative for example in this case The fear that 1st charity should be a or B As there is there should be necessary that GM is all this in end of the last 3 shots that are just continues fraction of things Exact sequence of exactly sectors and this means that the ground CGE should necesidad president then really get was increased for all of this pronounced Of for all members of the inca it gives a table which speeds which presents for each The ground we is at present in full insisting on what is then and it would a disease logical expression and if a logical expression is true we can have fish and is known as the ink from he and when we fish and with thing from here we can do it should use an actual integral expression but it a desired can be of false across our logical expressions along false positives
General idea so by this challenge is how to do this in general case in this case is there any evidence about to do this in general case is not so easy
Let's at 1st was considered in the existing approaches for such a q-gram extraction as the 1st is this whole paper quantify optical expression and it's an general and this paper is still widely differences in I suspect state of hard work involves this problem the insured's this method is so we extract only continuous think fraction from general expression
And it ignores the other part is in some way and then we does forms is continued fractions too much too much announced and when we and logical it's the expression of months ago and so we can use inverted index let's consider some examples
Reason for this example that will expression immediately following the heat and seeing it contains all consist of logical operations continuous things and there there is a symbol it's me share can be defeated amount of time reading the present it as the 1st Irish festival child of each chapter Then redeploy staff is now now in general means that it is something that we don't know what So On those then If we have some sink we don't know what's on that all because it's where we actually don't know what it is is there whole at the and that is that as the responding parliament or we'll be presence a is not About when know is a child of That in just a moment now because know there's this spot is present and if something kind of know what we can just movement But Also we can use some unnecessary elements and then replaces it this series of some q-grams grounds for example if the pretty grounds
Another approach to that of the existing approach was the rule quantity which will constitutional was larger unit before 6 and a Google tourists some of the was separate that's article expressions charts on open source this what's really interesting for me when I found it and I serves the Google guys so small that it can be as it this is a dualistic mentions of was the requirement of source code and it also seems to me that is the dual something better than was a paper sums and more smart about we don't know what
Actually we didn't know what is a good thing I'm still We will constitute closes and then Google engineer buzzcocks publishing industry description of the all of these indexing techniques being gender generated docile isn't dwelled on she's website so it was more than 5 years of from the when we can use Google Code shows and those in don't know all the normal how it works now have confused google customers but now we know how how it approaches
So in the description of the method it's get cut at 5 Tenoch statistics about each part of regular expression expensive it's as wouldn't we should present again this is part of the goal expression be much but since the and to think or not exact probably as this Uh part of regular expression only matters to some exact set of things as in the fields of property exactly as in graphics and suffered some means that has a single expression necessary medical foreseen to to have some prefix and suffix and much means that the that the integral expression part acquire something to be even any part of their much interesting and then is the day it personally union this charity 6 of the dual expression by some rules and used in that in the case of underground for query relations this index is really similar to busy challenges
Some examples to refer to the same integral expression as in the 1st example At 1st we get properties for and seniors streams so it's easy use as exact when we apply the blossom symbol then there was this so so is this expression tries to friends thing to have this preference and the itself so it's pretty easy and relatively Challenges at the start of regular expression and reading object the profits and then we are added to the end of things we are added to the Suffolk Zeng transformation so we get 6 of their bodies suppression and then we can easily transform it to as a logical expression on the ground
OK now we consider the existing approach and I would like to close the proposal messages and message which I propose for use
My message is not based on the analysis of the General administration but based on analysis of the corresponding what and transform it into some of the modern like not but these graphs have nots geneticists on each box but the grounds As then they could possibly simplifying as the graph and then use the in indexes so it's quite difficult to explain the whole message in before money then I would like to explain on the example
Let's consider some general expression The visible expression the charity aid is that the theory that any amount of judged to be at least one-third iteratively or the And in the end it faced challenges in the z is the corresponding button part for this little expression And now we can start our transformation
The 1st step is easy you just initial state of results graph The Ends then we start to western and grows this is often not a key the key is that of 2 things at 1st where over the lost it either a red characters and is the number of the state where the example for initial state of what the model we can indeed judged and then checked being in the state to solve our is good is going into a state 2 and last uh that's geneticists was be Similar but we can it's just stadium and millions of states for And so on because is seen the state religion and maybe is in the state for As presented Ausubel keys for the initial stage and then you should look into work really uh what another space we can add each from this Of for if we are in generative in state tool and last Texas was being according to a source of the model of again uh the Chechen be as this means that the ground ADD necessary present insisting and then the last uh the chance is Texas is being and we we asked you in the state to According to another are called note of the model we also can reach state for life by saying the ground and the same lost taxes But Also we can Each entity from State for long and you've lost that charges was here is that the grammar ATV necessary prison insisting and then lost their chances usability and state 5 And the important moment in his this is that Corresponding state of ideas what the model is finally zen corresponding state over as it is not single is also markets as final And really do similar thing for another And then when we have finished processing As the initial states Really that processing is its state reach that was estimated by News Is We've done Use of self reference and are also the state to bands that we can use it to ground and the leaf in this in the same space It's very real G. self-referencing So this is of the summation of discredit tool life and the idea is understandable Then we get some results and but this important property of this graph so I Something is much to it expression and much put in automatic is then we can arose from the initial that state of resulting off to final state of the this results in graph by only progress and he Z parts reach the guns is in his present instinct of solar this property ask to the z is that God is logical expression on the ground in users users songs that use the described the message of the god of medical expressions such as the this is result could be simplified because we can't age from here to here you needed ATV might also be a requirement in diagram ETD souls
It should be we also can used is this white AD and the leading to the ground but it doesn't matter if just ADD is enough so we can simplify As
As it implemented simplification techniques used to collect the full amount and this motherx it present all forcible minimal passes reach can be in gasses from additional state to final state and the semantics can be easily transformed by What does that do not logical expressions for the examples here for the 1st being the only on what is for all of the ground baby then immediately got his 1st someone There is a 2nd line of this table the neurons in the the media and this means that the 2nd someone is that the BBC and be the exams and so on for another lines of the table
Some comparisons all the different difference of the grants logical expression extraction from expression For single expression so far so fast that it was expression engine z sharp got is free and then extract the angle expression only containing some only containing kind seniors fraction of the will of course George nested good food usual more competences expression and my message that you some similar In logical expression but the model in such a simple form interest some duplication
Another example because there is no continual fraction of the incan because see the blast and the C plus 3 would be place it is null and then model the grounds can be extracted no continuous becomes can be extracted from here in the feeling of guns the experts sums and local search can see is that ABC and the figure on should be present and the minus of see something more not only in the museums in the but also this should be missing you was the right of the figure on the city and this is the As it were also some examples so we're not Nazar free method and local search method can extract any the around so we will search is confused by this stuff And inside plus it's probably too complicated because it can can see any features suffix because this figure of this strategy can be used the that any amount of biomass including as the amount of time Also some examples where inevitable will efficient guns and do something
And the performance is also on the need being a paper titles This summer It integral expression for example it's not their life at specimens of something kind I write for the best in in very can see some pretty dramatic the difference between index gone and seagoing strong And also we can see is that a time is inclusive when it will expression becomes longer is because of the longer that expression really can extract more what the grounds for for it and there you should more of course increase This is also a avoidable because really if we reconsider the you of the grounds was then being caught it also some was then you think more false-positive bots of fitting tool ready to list all was increased so those of us some optimization of possible even if we don't know what's in the future of the ground we can do anyway decide to expose some of the GM form always search But
Work-in-progress large was was that the user might increase the spices basic on pgce ads in the country model anything but this this is welcome
This is work in progress and those that I asked you a some problems in As the 1st problem is transforming graph would be with a large So in this case And mediated wasn't really sure decides that when performing graphs that each some size of initial states that we should start during its Andalusia most of whom the Also a process of simplification could produce where large title of possible losses in this case you really probably should done tied to the case stable but use as a just transforming graph And also is a shift grounds for this particular task is not optimal and so would be better to use variable and So in my presentation I some simplification for more easier to understand them and I would like to mention is that in order to minimize the presentation wouldn't be at this information for whole somebody I didn't mention the difference between the deterministic and moral nondeterministic what the model So the deterministic automata can have on the run are market use the same generated from the same state then read you'll share only reason nondeterministic of what the model marketable expression engines actually transforms nondeterministic all the multiple deterministic another to do foster much because in deterministic optimal optimal but the 1 state can be be effective at the same time it's really good for performance also in your life radical expression engines don't Use the mark box this is the exact selective because for example would be there could be some met the symbol of the co-expression reach for example at present In a I'm not majority or in a space shuttle or just a new water generative ends this means is that I was there will be a really many arcs and indicated was person engines group geneticists in college Colors is a group of churches reach Indistinct above by it'll expression And also that it was Bishop engines have some special Method for for him in the start and end of the ink was of course think all the line of Insurance it's going to be done the body Representation start and end as some special challenges for example in Our in our example Howard of expression while we didn't use some stuff and and justice but said it goes persons since users
My project also need some help by means of assisting collagen and the article person from video life tasks who proved the effectiveness of money of all and also find in some corner cases and So if you have some of datasets for me it would be great you shift from the mean
So think you for attention ask you questions please Game by Answer because we already 15 exists on diagrams implemented in Prolog both positive But it will it could be it that so for example diagrams for evidence and you freakin a weight problem these and it would be better to use variable and instruments And the rest of his life while you were yes those that it's almost all of the rest of you using that that's so that you have a questions about solution of q and q becomes a lot and number of it is available at the beginning of the all day in his eyes which plants will be based on that same thing If there actually not that this was found in the 3rd stage of life that you have to with that of me The The You said that violence youth index reached contains as for example the most of the guns and foreground yes it's also interesting possible approach Later on
This example with me spectacles like what we find out what's next class of this OK I you want can you represent the as I about it that generate about whether that in the but on
Are you asking for all of them and you can fall is that logical expressions on the grounds for for that examples of these areas all of this uh actually actually not because he each just ignore us as is Jonathan because to to many charities how much and continue this age I said that it's a slower just because the longer is longer than It's not because of this project but because of their whole number of grams of another part is larger and book they have is their and data security and logic was increased and because of this the Has he said we have work I was not if we I have a more complicated expression on diagrams Ieee forever but less false positives so I get less efficient the heat but I get more and more I have to admit more cost increases and there is a trade-off between the amount of false positives in the inputs and the use of yes yes have some are there were from both increased is last and also it's done at inference is therefore also boys is if linear might say this sum is timation I should decide not to do that was in peace and you move it from a logical expressions in other questions to do what I used the it's possible you might be able to differences that EGG rjm converts most abiogenesis who was the 1st some years it is also possible to to do with the group to be looking its own multiple alternative is that we'll have to wait as they do is rather than it be a lot some additional size findings but it's differently possible and also it will fill some dimensions of advantages and the cost for example you in the ground and you would like to Find things as that continuous some that the guy on the beach as this the gun starts and you can this using so much when you have questions you can do so so this is what would be a was to be a better solution particular of on I didn't say is that the costs of while it's not normal of my book is just the same EEG judging index associated sees him any other questions in this area but it will be years this gesture about justice but the it's not so easy to implement August because they're kind or expected that collects inside 6 is not dependent on index now on and also on our from user interface methods also for an index implementation you can't get any statistic information that do problems but this is a journey the with colored Statistik about it they ground when we felt that is put in in index and can I did suspect systems from and function and do this optimization news is that it is the right way and I would like to do Any other questions it seems it's not working out Learning how often it so all of them is that The following 4 years so that literal expressions for weekend uh extract any of the grounds is in this case the region that should a sum of sequential Scott for example if you are searching using Gini index z blunder coral extract query on the spatial of and if was there exists extract query say is if I can do I can do something that in full and expand this decide to don't don't do and an index gone and the sequential scan reaches fosters full in is this Case so if we had a fair and a good expressions expressions reach a where for each multigrams can be extracted you just have to fall back to sequential stuff I think it's a little hard unintelligible any other questions Again
There you you you know better than the power of This Rule and the link to the study of all of there are Basically is the question of how you think about the But I actually present in memory is the
This table so I arises logical expression only for a better explanation but I just thought it that iterate over lines of Table and check if all levels in the GM these markets is not actually present in the this thing if it is so I started off as a penetrating and the same is it is obvious to us so this thing possibly much article expression and if I these at end of table result is Ayatollah falls as this means the thing definitely don't much in the middle position the year you that there is a Already existing competitor imposed a scale I just found this operator you apparatus of at a glance in the G. content and the model my precious contains these additional line in that a skill for any other questions is is the way you minutes information so that you need me negative measures for example you're decides that Some stink they reach much bigger expression should definitely it doesn't contain something yes the means of Forcibly about this integral expressions should be because benefits expression and suffix that was there so even the socialization of children actually contain some parts of it can be it can contain anything that mean if if it works expression and things this part of the world as long as possible all flow of this but if we don't allow users read research some particular class or the bottom function and so the cost of a lot more monopoly bottom function because there is a mole to negative and the increases uses easier was submitted to find some better ways to lose simplification because its moment but it's simplifies all analyzes Any other questions it seems that no questions in the 1st half of the