I read the Wikipedia and am having a hard time getting this concept to click. Of course I could ask chatGPT but this community is more fun!
Can I get this concept simplified with a couple real world examples?
One common use is "...to allow fast full-text searching."
The two types denote directionality. One takes you forward through the index, and the other takes you backward (the inverse) through the index. That's it. There's no mystery to uncover here. Otherwise the two types are identical, it's just a question of what information you have, and as a result what information you're trying to find.
To address your inquiry, I don't think there's actually a way to know why the use is what it is today. The only reason it's important to define which is forward and which one is inverted is so that we can all have a conversation about them, and everyone knows which direction we're talking about. Think about the terms "left" and "right": they are relative. Which is which doesn't matter, except that everyone needs to agree which one is "left" and which one is "right" in order for the words to have meaning. If, as a culture, we decided to flip left and right, then you'd have the same issue figuring out what a "right turn" vs a "left turn" is since the agreed upon meaning had changed. However, the naming is arbitrary, so which one is which (in and of itself) doesn't matter - what matters is that we all agree on the meaning.
In your comment where you ask, "please don't just define the terms", you're missing the point, and I think you're just getting hung up on the wording when there is absolutely no difference between them.
For the benefit of future readers, I will now provide several "forward" and "inverted" index examples:
Example 1: Web search
If you're thinking that the inverse of an index is something like the inverse of a function in mathematics, where the inverse is a special thing that has a different form, then you're mistaken: that's not the case here.
In a search engine you have a list of documents (pages on web sites), where you enter some keywords and get results back.
A forward index (or just index) is the list of documents, and which words appear in them. In the web search example, Google crawls the web, building the list of documents, figuring out which words appear in each page.
The inverted index is the list of words, and the documents in which they appear. In the web search example, you provide the list of words (your search query), and Google produces the documents (search result links).
They are both indexes - it's just a question of which direction you're going. Forward is from documents->to->words, inverted is from words->to->documents.
Example 2: DNS
Another example is a DNS lookup (which takes a host name, and returns an IP address) and a reverse lookup (which takes an IP address, and gives you the host name).
Example 3: A book
The index in the back of a book is actually an inverted index, as defined by the examples above - a list of words, and where to find them in the book. In a book, the table of contents is like a forward index: it's a list of documents (chapters) which the book contains, except instead of listing the words in those sections, the table of contents just gives a name/general description of what's contained in those documents (chapters).
Example 4: Your cell phone
The forward index in your cell phone is your list of contacts, and which phone numbers (cell, home, work) are associated with those contacts. The inverted index is what allows you to manually enter a phone number, and when you hit "dial" you see the person's name, rather than the number, because your phone has taken the phone number and found you the contact associated with it.
They called it inverted just because there is already a forward index. Take the example of search engine, it composed by two parts: the first part is "web crawler and parser" which build a index from document to word, the second part is search database which build a index from word to document. Because of the first index exist, we naturally call the second index as inverted index.
If you name the TOC (Table of Content) of a book as index, then you should call the index at the end of book as "inverted index". Or, in other side, you can call the TOC as inverted index.
Here is an array:
- A[0] = Alice
- A[1] = Bob
- A[2] = Charlie
Here 0,1,2 are indices.
Now suppose that we want to know which index contains a given word. Then we use a dictionary:
- D[Alice] = 0
- D[Bob] = 1
- D[Charlie] = 2
This is an inverted index (according to your Wikipedia quote).
The word index has different meaning in different contexts:
- Technical books often have an index of terms at the end.
- The Catholic church held an index of forbidden books.
- In economics, there are financial indices.
- In computer science, an index is usually an integer used to index into an array.
The reason why we use the term "inverted index" is that the term "index" came to computer science first. In fact, it has several common meanings in computer science, but in this case it refers to the more general concept of an efficient lookup data structure for a database.
What we call an "inverted index" is, strictly speaking, an inverted file used as a database index. "Inverted file" is the data structure, and "index" is the use to which it is put. A B-tree data structure, similarly, can be put to more uses than just database indexing, but it makes sense to talk of a "B-tree index".
The index in a book is not the only kind of text index. Strong's Concordance, which is considered an important ancestor of modern full-text search, is a permuted index (specifically, a variant known today as a KWIC index).
The inverted file is not the only data structure that can be used for text/string indexing. Suffix arrays and Burrows-Wheeler indexes are commonly used for strings that don't need linguistic analysis such as indexing DNA or RNA sequences. Some of these index variants have efficient partial match queries.
The signature file (a probabilistic index structure, essentially Bloom filters for text search) was briefly popular, but it turned out to be nowhere near as generally useful as its competitors.