Inverted index: Difference between revisions

{{task|Classic CS problems and programs}}[[Category:Search]]

An [[wp:Inverted_index|Inverted Index]] is a data structure used to create full text search.

 

 

=={{header|Ada}}==

Here is the main program (file inverted_index.adb):

 

use Ada.Text_IO;

 

end;

end loop;

 

A sample output:

 

Enter one or more words to search for; <return> to finish:

Found in the following files: 0.txt, 1.txt, 2.txt

 

The real work is actually done in the package Generic_Inverted_Index. Here is the specification (file generic_inverted_index.ads):

 

private with Ada.Containers.Indefinite_Hashed_Maps;

 

type Storage_Type is new Maps.Map with null record;

 

 

Here is the implementation (generic_inverted_index.adb):

 

 

use Source_Vecs;

end Same_Vector;

 

 

===Package Parse_Lines===

The main program also uses an auxiliary package Parse_Lines. Note the usage of Gnat.Regpat, which itself is pattern matching package, specific for gnat/gcc. This package is derived from the [[Regular expressions#Ada|Ada implementation of the regular expressions task]]. Here is the spec (parse_lines.ads):

 

 

package Parse_Lines is

procedure Iterate_Words(S: String);

 

 

And here is the implementation (parse_lines.adb):

 

 

package body Parse_Lines is

end Iterate_Words;

 

 

===Alternative Implementation of Generic_Inverted_Index (Ada 2012)===

The new standard Ada 2012 simplifies the usage of containers significantly. The following runs under gnat (GNAT GPL 2011 (20110419)), when using the experimental -gnat2012 switch. The main program is the same. Here is the spec for Generic_Inverted_Index:

 

private with Ada.Containers.Indefinite_Hashed_Maps;

 

type Storage_Type is new Maps.Map with null record;

 

 

The implementation:

 

-- uses some of the new Ada 2012 syntax

use Source_Vecs;

end Same_Vector;

 

 

=={{header|AutoHotkey}}==

{{works with|AutoHotkey_L}}

 

inputbox, files, files, file pattern such as c:\files\*.txt

 

Loop, %files%, 0,1

{

wordList := WordsIn(A_LoopFileFullPath)

}

 

 

WordsIn(docpath)

FileRead, content, %docpath%

spos = 1

this_wordList .= match "`n"

}

}

 

global word2docs

 

if A_loopField =

continue

else

return word2docs[word2find]

 

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

This uses a hashed index and linked lists to hold the file numbers.

FileList$() = "BBCKEY0.TXT", "BBCKEY1.TXT", "BBCKEY2.TXT", \

\ "BBCKEY3.TXT", "BBCKEY4.TXT"

DictSize% = 30000

DIM Index{(DictSize%-1) word$, link%}

REM Build inverted index:

FOR file% = DIM(FileList$(),1) TO 0 STEP -1

F% = OPENIN(filename$)

IF F% = 0 ERROR 100, "Failed to open file"

WHILE NOT EOF#F%

REPEAT C%=BGET#F% : UNTIL C%>64 OR EOF#F% : word$ = CHR$(C%)

REPEAT C%=BGET#F% : word$ += CHR$(C%) : UNTIL C%<65

word$ = FNlower(LEFT$(word$))

hash% = FNhash(word$)

WHILE Index{(hash%)}.word$<>"" AND Index{(hash%)}.word$<>word$

ENDIF

ENDWHILE

CLOSE #F%

NEXT file%

REM Now query the index:

PRINT FNquery("random")

PRINT FNquery("the")

END

DEF FNquery(A$)

LOCAL hash%, link%, temp%

ENDWHILE

= LEFT$(LEFT$(A$))

DEF FNhash(A$)

LOCAL hash%

IF LEN(A$) > 4 hash% EOR= !(!^A$ + LEN(A$) - 4)

= hash% MOD DictSize%

DEF FNlower(A$)

LOCAL A%,C%

IF C% >= 65 IF C% <= 90 MID$(A$,A%,1) = CHR$(C%+32)

NEXT

'''Output:'''

<pre>

=={{header|C}}==

The code is stupidly long, having to implement a Trie to store strings and all -- the program doesn't do anything shiny, but Tries may be interesting to look at.

#include <stdlib.h>

 

int chr_idx[256] = {0};

char idx_chr[256] = {0};

#define FNAME 0

typedef struct trie_t *trie, trie_t;

struct trie_t {

};

trie trie_new() { return calloc(sizeof(trie_t), 1); }

#define find_word(r, w) trie_trav(r, w, 1)

/* tree traversal: returns node if end of word and matches string, optionally

trie trie_trav(trie root, const char * str, int no_create)

{

}

/* complete traversal of whole tree, calling callback at each end of word node.

* similar method can be used to free nodes, had we wanted to do that.

int trie_all(trie root, char path[], int depth, int (*callback)(char *))

{

}

void add_index(trie root, const char *word, const char *fname)

{

}

int print_path(char *path)

{

}

/* pretend we parsed text files and got lower cased words: dealing *

* with text file is a whole other animal and would make code too long */

const char *files[] = { "f1.txt", "source/f2.txt", "other_file" };

const char *text[][5] ={{ "it", "is", "what", "it", "is" },

trie init_tables()

{

 

/* Enable USE_ADVANCED_FILE_HANDLING to use advanced file handling.

* You need to have files named like above files[], with words in them

*/

#define USE_ADVANCED_FILE_HANDLING 0

#if USE_ADVANCED_FILE_HANDLING

 

#else

#endif /*USE_ADVANCED_FILE_HANDLING*/

 

}

void search_index(trie root, const char *word)

{

}

int main()

{

Search for "is": f1.txt other_file source/f2.txt

Search for "banana": other_file

 

=={{header|C sharp|C#}}==

using System.Collections.Generic;

using System.IO;

Console.WriteLine("{0} found in: {1}", find, string.Join(" ", Invert(dictionary)[find]));

}

Sample output:

find: what

 

=={{header|Clojure}}==

(:require [clojure.set :as sets]

[clojure.java.io :as io]))

(defn term-seq [text] (map normalize (re-seq pattern text)))

 

"Produces map with v added to the set associated with key k in map m"

[m k v] (assoc m k (conj (get m k #{}) v)))

(defn search [index query]

(apply sets/intersection (map index (term-seq query))))

 

=={{header|CoffeeScript}}==

fs = require 'fs'

 

console.log "#{fn}:#{line_num}"

console.log "\n"

get_words = (line) ->

words = line.replace(/\W/g, ' ').split ' '

grep index, 'make_index'

grep index, 'sort'

output

locations for 'make_index':

inverted_index.coffee:3

inverted_index.coffee:35

knuth_sample.coffee:12

 

=={{header|Common Lisp}}==

(:use cl))

(in-package rosettacode.inverted-index)

:test #'equal))

 

Example:

(defparameter *query* "foo bar")

(defparameter *result* (lookup *index* *query*))

 

=={{header|D}}==

 

void main() {

writefln("'%s' not found.", w);

}

Both the demo text files and the queries are from the Wikipedia page, they contain:

It is what it is.

Enter a word to search for: (q to quit): q

quitting.</pre>

 

=={{header|Erlang}}==

Ditto for any other character.

 

-module( inverted_index ).

 

lists:foldl( fun import_from_file/2, dict:new(), Files ).

 

[Files | T] = [dict:fetch(X, Inverted_index) || X <- Binaries],

lists:foldl( fun search_common/2, Files, T ).

import_from_file( File, Dict_acc ) ->

New_dict = dict:from_list( import_from_file_contents(File, file:read_file(File)) ),

 

import_from_file_contents( File, {ok, Binary} ) ->

[{X, [File]} || X <- binary:split( Binary, binary:compile_pattern([<<" ">>, <<"\n">>]), [global] )];

import_from_file_contents( File, {error, Error} ) ->

 

 

search_common( Files, Acc ) -> [X || X <- Acc, lists:member(X, Files)].

 

=={{header|F Sharp|F#}}==

open System.IO

 

// Map search terms to associated set of files

type searchIndexMap = Map<string, Set<string>>

let inputSearchCriteria() =

let readLine prompt =

printf "%s: " prompt

Console.ReadLine().Split()

readLine "Files", (readLine "Find") |> Array.map (fun s -> s.ToLower())

let updateIndex indexMap keyValuePair =

let k, v = keyValuePair

match Map.tryFind k indexMap with

| None -> Map.add k (Set.singleton v) indexMap

| Some set -> Map.add k (Set.add v set) indexMap

let buildIndex files =

let fileData file =

File.ReadAllText(file).Split() |> Seq.map (fun word -> word.ToLower(), file)

files |> Seq.collect fileData

|> Seq.fold updateIndex Map.empty

let searchFiles() =

let files, terms = inputSearchCriteria()

|> Set.intersectMany

 

Sample usage:

<pre>

Find: what is

Found in: file1.txt file2.txt</pre>

 

=={{header|Go}}==

 

import (

}

return true

func ui() {

fmt.Println(len(index), "words indexed in", len(indexed), "files")

fmt.Println("one match:")

fmt.Println(" ", indexed[dl[0]].file, indexed[dl[0]].title)

fmt.Println(len(dl), "matches:")

for _, d := range dl {

}

}

Session:

<pre>

=={{header|Haskell}}==

 

import Data.Char (isAlpha, toLower)

import qualified Data.Map as M

intersections xs = foldl1 S.intersection xs

 

 

An example of use, assuming the program is named <code>iindex</code> and there exist files <code>t0</code>, <code>t1</code>, and <code>t2</code> with contents "It is what it is.", "What is it?", and "It is a banana.":

 

The following implements a simple case insensitive inverse index using lists simulating texts.

 

texts := table() # substitute for read and parse files

 

every textname := key(texts) do # build index for each 'text'

TermSearchUI(SII) # search UI

end

 

repeat {

writes("Enter search terms (^z to quit) : ")

 

terms ? while not pos(0) do {

tab(many(' \t'))

put(x,tab(upto('\ \t')|0))

}

}

write("End of search")

 

procedure TermSearch(ii,x) #: return set of matches or fail

( /u := ii[s] ) | (u **:= ii[s])

if *u > 0 then return u

every writes(s|!x) do writes(" ")

write()

 

Output:<pre>Enter search terms (^z to quit) : is it

 

The following code will build a full index. Modification of search routines is left as an exercise:

 

procedure FullInvertedIndex(ii,k,words) #: accumulate a full inverted index

 

return ii

 

=={{header|J}}==

This just implements the required spec, with a simplistic definition for what a word is, and with no support for stop words, nor for phrase searching.

 

 

rxutf8 0 NB. support latin1 searches for this example, instead of utf8

hits=. buckets{~words i.~.parse tolower y

files {~ >([-.-.)each/hits

 

Example use:

 

>search 'finally learning'

~help/primer/end.htm

~help/primer/gui.htm

>search 'around'

=={{header|Java}}==

package org.rosettacode;

 

public class InvertedIndex {

 

 

 

 

 

 

 

 

}

 

 

Example output:

indexed pg30637.txt 106473 words

indexed pg7025.txt 205714 words

olympian pg30637.txt

 

 

=={{header|jq}}==

 

'''Part 1: inverted_index and search'''

# construct a lookup table: { word: array_of_docs }

def inverted_index:

def overlap(that): . as $this

| reduce that[] as $item ([]; if $this|index($item) then . + [$item] else . end);

. as $dict

| if (words|length) == 0 then []

else reduce words[1:][] as $word

( $dict[words[0]]; overlap( $dict[$word] ) )

 

'''Part 2: Interactive Search'''

could create a temporary file to hold the parsed output.

 

"Enter a string or an array of strings to search for, quoting each string, or 0 to exit:",

else empty

end) as $in

| search($in), prompt_search ) ;

 

 

'''Example''':

Enter a string or an array of strings to search for, quoting each string, or 0 to exit:

"is"

Enter a string or an array of strings to search for, quoting each string, or 0 to exit:

0

 

=={{header|OCaml}}==

unix.cma bigarray.cma nums.cma -I +sexplib sexplib.cma str.cma \

inv.ml

ocamlc -o inv.byte unix.cma bigarray.cma nums.cma -I +sexplib sexplib.cma str.cma inv.cmo

 

 

type files = string array with sexp

| "--index-file", in_file -> index_file in_file

| "--search-word", word -> search_word word

 

=={{header|Perl}}==

 

# given an array of files, returns the index

foreach my $file (@files)

{

s/\A\W+//;

}

return %iindex;

my @words = @_;

my $res = set();

foreach my $w (map {lc} @words)

{

length $w < 3 and next;

exists $idx{$w} or return set();

# first arg is a comma-separated list of words to search for

print "$_\n"

 

}

}

 

=={{header|PicoLisp}}==

it is a banana</pre>

we can read them into a binary tree in the global variable '*MyIndex'

 

(use Word

(extract

'((Word) (val (car (idx '*MyIndex Word))))

Output:

<pre>: (searchFor "what" "is" "it")

: (searchFor "it" "is")

-> ("file3" "file2" "file1")</pre>

 

=={{header|Python}}==

 

First the simple inverted index from [[wp:Inverted index|here]] together with an implementation of a search for (multiple) terms from that index.

This implements: http://en.wikipedia.org/wiki/Inverted_index of 28/07/10

'''

terms = ["what", "is", "it"]

print('\nTerm Search for: ' + repr(terms))

 

'''Sample Output'''

 

<small>It is assumed that the following code is added to the end of the code for the simple case above and so shares its file opening and parsing results</small>

 

 

print(ans)

ans = Counter(ans)

 

'''Sample Output'''

 

=={{header|Racket}}==

#!/usr/bin/env racket

#lang racket

(printf "No matching files.\n")

(printf "Terms found at: ~a.\n" (string-join all ", "))))

{{out}}

<pre>

Terms found at: F1, F2.

</pre>

 

=={{header|REXX}}==

Note: In this algorithm, word indices start at 1.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

word ───60─── found in:

word ───don't─── found in:

word ───burma-shave─── found in:

</pre>

 

 

'''indexmerge.rb'''

@data = Marshal.load open("index.dat")

else

open("index.dat", "w") do |index|

index.write Marshal.dump(@data)

 

'''indexsearch.rb'''

@data = Marshal.load open("index.dat")

else

end

 

 

'''Output'''

> ./indexsearch.rb It iS\!

["file1", "file2", "file3"]</pre>

=={{header|Scala}}==

import java.io.File

 

}

}

{{out}}

<pre>> InvertedIndex "the" file1.txt file2.txt file3.txt

 

=={{header|Tcl}}==

proc wordsInString str {

# We define "words" to be "maximal sequences of 'word' characters".

array set localidx {}

foreach word [wordsInString $data] {

}

 

# Transcribe into global index

foreach {word places} [array get localidx] {

}

}

global index

if {[info exists index($word)]} {

}

}

set files [findFilesForWord [lindex $words 0]]

foreach w [lrange $words 1 end] {

}

return $files

set files {}

foreach w $words {

}

dict for {file places} $index([lindex $words 0]) {

}

return $files

For the GUI:

pack [labelframe .files -text Files] -side left -fill y

pack [listbox .files.list -listvariable files]

pack [entry .found.entry -textvariable terms] -fill x

pack [button .found.findAll -command FindAll \

pack [button .found.findSeq -command FindSeq \

 

# The actions invoked by various GUI buttons

set f [tk_getOpenFile]

if {$f ne ""} {

}

}

set fs [findFilesWithAllWords $words]

lappend found "Searching for files with all $terms" {*}$fs \

}

proc FindSeq {} {

set fs [findFilesWithWordSequence $words]

lappend found "Searching for files with \"$terms\"" {*}$fs \

 

=={{header|TUSCRIPT}}==

$$ MODE TUSCRIPT

 

ENDLOOP

PRINT "-> ",files

Output:

<pre>

{{works with|ksh93}}

 

 

typeset -A INDEX

(( count == $# )) && echo $file

done

 

Example use:

search hello world

 

===Directory on filesystem===

* Add note about slowness.

 

# index.sh - create an inverted index

 

# the record separator for $INDEX/all.tab).

for file in "$@"; do

done

 

fi=1

for file in "$@"; do

 

 

 

 

 

# search.sh - search an inverted index

 

want=sequence

while getopts aos name; do

done

shift $((OPTIND - 1))

 

all() {

}

 

one() {

}

 

sequence() {

}