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|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|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|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 (

"bytes"

"fmt"

"os"

)

 

// inverted index representation

var indexed []doc

 

}

 

df, err := os.Open(dir)

if err != nil {

}

if len(fis) == 0 {

}

indexed := 0

for _, fi := range fis {

indexed++

}

 

// scan lines

lines := 0

for {

b, isPrefix, err := r.ReadLine()

switch {

return true

case err != nil:

return true

case isPrefix:

return true

case lines < 20 && bytes.HasPrefix(b, []byte("Title:")):

}

}

Session:

<pre>

enter single words to search for

enter a blank line when done

=={{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|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

List.iter (fun (w, from) -> Hashtbl.replace h w from) inv_index;

List.iter (fun w ->

) words;

Hashtbl.fold (fun w from acc -> (w, from) :: acc) h []

| "--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'''

The phrase is found most commonly in text: 'T0.txt'</pre>

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

</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|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() {

}