Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The <a href="http://www-igm.univ-mlv.fr/~lecroq/string/index.html" rel="noreferrer">http://www-igm.univ-mlv.fr/~lecroq/string/index.html</a> link you point to is an excellent source and summary of some of the best known and researched string matching algorithms.</p> <p>Solutions to most search problems involve trade offs with respect to pre-processing overhead, time and space requirements. No single algorithm will be optimal or practical in all cases.</p> <p>If you objective is to design a specific algorithm for string searching, then ignore the rest of what I have to say, If you want to develop a generalized string searching service routine then try the following:</p> <p>Spend some time reviewing the specific strengths and weaknesses of the algorithms you have already referenced. Conduct the review with the objective of finding a set of algorithms that cover the range and scope of string searches you are interested in. Then, build a front end search selector based on a classifier function to target the best algorithm for the given inputs. This way you may employ the most efficient algorithm to do the job. This is particularly effective when an algorithm is very good for certain searches but degrades poorly. For example, brute force is probably the best for needles of length 1 but quickly degrades as needle length increases, whereupon the <a href="http://userweb.cs.utexas.edu/users/moore/publications/sustik-moore.pdf" rel="noreferrer">sustik-moore algoritim</a> may become more efficient (over small alphabets), then for longer needles and larger alphabets, the KMP or Boyer-Moore algorithms may be better. These are just examples to illustrate a possible strategy.</p> <p>The multiple algorithm approach not a new idea. I believe it has been employed by a few commercial Sort/Search packages (e.g. SYNCSORT commonly used on mainframes implements several sort algorithms and uses heuristics to choose the "best" one for the given inputs)</p> <p>Each search algorithm comes in several variations that can make significant differences to its performance, as, for example, this <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.7176&amp;rep=rep1&amp;type=pdf" rel="noreferrer">paper</a> illustrates.</p> <p>Benchmark your service to categorize the areas where additional search strategies are needed or to more effectively tune your selector function. This approach is not quick or easy but if done well can produce very good results. </p>
    singulars
    1. This table or related slice is empty.
    1. POWhat is the fastest substring search algorithm?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USNealB
    1. USNealB
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThanks for the response, especially the link to Sustik-Moore which I hadn't seen before. The multiple algorithms approach is surely in widespread use. Glibc basically does strchr, Two-Way without bad character shift table, or Two-Way with bad character shift table, depending on whether needle_len is 1, <32, or >32. My current approach is the same except that I always use the shift table; I replaced the 1kb memset necessary to do so with a 32 byte memset on a bitset used to mark which elements of the table have been initialized, and I get the benefit (but not overhead) even for tiny needles.
      singulars
      1. PO
      1. USR..
    2. COAfter thinking about it, I'm really curious what the intended application for Sustik-Moore is. With small alphabets, you'll never get to make any significant shifts (all characters of the alphabet almost surely appear near the end of the needle) and finite automata approaches are very efficient (small state transition table). So I can't envision any scenario where Sustik-Moore could be optimal...
      singulars
      1. PO
      1. USR..
    3. COgreat response -- if I could star this particular answer I would.
      singulars
      1. PO
      1. USJason S
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload