Indexing with substrings - Department of Computer Science
Indexing with substrings
Ben Langmead
Department of Computer Science
You are free to use these slides. If you do, please sign the guestbook (teaching-materials), or email me (ben.langmead@) and tell me briefly how you're using them. For original Keynote files, email me.
Preprocessing
We saw the naive algorithm and Boyer-Moore. These and other algorithms can be distinguished by the kind of preprocessing they do.
Naive algorithm does no preprocessing Nothing for algorithm to do until it is given both pattern P and text T
Boyer-Moore preprocesses the pattern P If P is provided first, we can build lookup tables for the bad character and good suffix rules If T1 is provided later on, we use the already-built tables to match P to T1 If T2 is provided later on, we use the already-built tables to match P to T2 ...
Indexing
Can preprocess P, T or both. When preprocessing T, we say we are making an index of T, like the index of a book.
Sometimes called inverted indexing, since it inverts the word/page relationship
(publishing)#mediaviewer/ File:Atlas_maior_1655_-_vol_10_-_Novus_Atlas_Sinensis_-_index_-_P1080375.JPG
Web seach engines also use inverted indexing
Documents:
T[0]
=
"it
is
what
it
is"
T[1]
=
"what
is
it"
T[2]
=
"it
is
a
banana"
Index:
"a":
[2]
"banana":
[2]
"is":
[0,
1,
2]
"it":
[0,
1,
2]
"what":
[0,
1]
Substring index
To index T:
Extract sequences from T (usually substrings), along with pointers back to where they occurred
Organize pieces and pointers into a map data structure. Various map structures are possible, all involving some mix of grouping / sorting.
T: C G T G C C T A C T T A C T T A C A T
Substring 1: C G T G C Substring 2: C C T A C Substring 3: C T T A C Substring 4: C T T A C
Index, sorted by key
C C T A C : offset=4 C G T G C : offset=0 C T T A C : offsets=8, 12
Substring index
To query index with P:
Extract substrings from P. Use them to query the index. Index tells us where they occur in T.
For each occurrence, check if there is a match in that vicinity
T: C G T G C C T A C T T A C T T A C A T
Index hit 2
Index hit 1
P: C T A C T T A C
Substring 1: C T A C T
x
Substring 2: T A C T T x
Substring 3: A C T T A x
Substring 4:
CTTAC
Index, sorted by key
C C T A C : offset=4 C G T G C : offset=0 C T T A C : offsets=8, 12
Index lookups
See Python example:
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- python programming exercises 4 was bi
- python count number of occurrences of a substring in string
- suffix trees carnegie mellon university
- problem statement
- ben langmead department of computer science
- gaurav kr suman mat7
- tries and string matching stanford university
- computer science i sample program substring search please check
- python with ip class 12 assignment prerequisite part 2 read jps noida
- suffix trees department of computer science
Related searches
- careers with a computer science degree
- list of computer science topics
- benefits of computer science degree
- history of computer science pdf
- jobs with computer science degree
- fundamentals of computer science pdf
- benefits of computer science career
- benefits of computer science education
- doctor of computer science salary
- examples of computer science math
- list of computer science journals
- examples of computer science projects