Inverted index: Difference between revisions

{{trans|D}}

F parse_file(fname, fcontents)

print(‘'#.' found in #..’.format(w, sorted(Array(index[w]))))

E

{{out}}

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

use Ada.Text_IO;

end;

end loop;

A sample output:

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

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"

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>

search_index(root, "boo");

return 0;

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|C++}}==

Same idea as the C implementation - trie to store the words

#include <algorithm>

#include <fstream>

return 0;

}

{{out}}

<pre>

=={{header|Clojure}}==

(:require [clojure.set :as sets]

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

(defn search [index query]

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

=={{header|CoffeeScript}}==

fs = require 'fs'

grep index, 'make_index'

grep index, 'sort'

output

> coffee inverted_index.coffee

locations for 'make_index':

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.

{{libheader| system.Generics.Collections}}

{{libheader| SYstem.IOUtils}}

program Inverted_index;

Index.Free;

Input: Same of [[#D|D]].

{{out}}

===Indexing===

Index values are sets associated with each word (key). We use the local-put-value function to permanently store the index, in the browser local storage.

;; set of input files

(define FILES {T0.txt T1.txt T2.txt})

(let ((text (text-parse text)))

(for ((word text)) (invert-word (string-downcase word) file INVERT))))

=== Query ===

Intersect sets values of each word.

;; usage : (inverted-search w1 w2 ..)

(define-syntax-rule (inverted-search w ...)

(set-intersect res (local-get-value word INVERT)))

FILES words))

Output :

(map-files invert-text FILES)

(inverted-search is it)

(inverted-search boule)

[3]→ null

=={{header|Erlang}}==

Ditto for any other character.

-module( inverted_index ).

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

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

open System.IO

|> Set.intersectMany

Sample usage:

<pre>

=={{header|Factor}}==

sets splitting vectors ;

IN: rosettacode.inverted-index

: query ( terms index -- files )

[ at ] curry map [ ] [ intersect ] map-reduce ;

Example use :

--- Data stack:

( scratchpad ) { "what" "is" "it" } swap query .

V{ "f1" "f2" }

=={{header|Go}}==

import (

}

}

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

write()

return

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;

}

Example output:

java -cp bin org.rosettacode.InvertedIndex "huntsman,merit,dog,the,gutenberg,lovecraft,olympian" pg30637.txt pg7025.txt pg82.txt pg9090.txt

indexed pg30637.txt 106473 words

olympian pg30637.txt

=={{header|jq}}==

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

# construct a lookup table: { word: array_of_docs }

def inverted_index:

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:",

( (input | if type == "array" then . elif type == "string" then [.]

| 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|Julia}}==

idx = Dict{String, Dict}()

for file in files

const searchterms = ["forehead", "of", "hand", "a", "foot"]

wordsearch(didx, searchterms)

=={{header|Kotlin}}==

import java.io.File

findWord(word)

}

Contents of files:

=={{header|Mathematica}}/{{header|Wolfram Language}}==

Manipulate[Grid[sr = TextSearch[si, ToString[s]];

{FileBaseName /@ Normal[Dataset[sr][All, "ReferenceLocation"]],

Column[#, Frame -> All] & /@ sr[All, "Snippet"]} // Transpose,

{{out}}

Outputs a graphical user interface with an interactive input field showing filename and the snippet of text that includes the search string.

We have used as examples three files containing the text from Wikipedia article. We used here an index which keep document name and line number. It would be easy to add the position in the line.

type

stdout.write &"... in “{docName}”, line{plural(linenums.len)}"

for num in linenums: stdout.write ' ', num

{{out}}

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

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

print "$_\n"

=={{header|Phix}}==

Might be better (and almost as easy) for the dictionary values to be say

{total_count, {file nos}, {file counts}}.

<span style="color: #000080;font-style:italic;">-- demo\rosetta\Inverted_index.exw</span>

<span style="color: #008080;">without</span> <span style="color: #008080;">js</span> <span style="color: #000080;font-style:italic;">-- (file i/o)</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">lookup</span><span style="color: #0000FF;">({</span><span style="color: #008000;">"dir"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"lower"</span><span style="color: #0000FF;">})</span> <span style="color: #000080;font-style:italic;">-- should be the same two</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">lookup</span><span style="color: #0000FF;">({</span><span style="color: #008000;">"ban"</span><span style="color: #0000FF;">&</span><span style="color: #008000;">"anafish"</span><span style="color: #0000FF;">})</span> <span style="color: #000080;font-style:italic;">-- should be none ({})</span>

{{out}}

Note the distributed version has been modified and is occasionally used for real, so the output will likely differ.

=={{header|PHP}}==

function buildInvertedIndex($filenames)

echo "Unable to find the word \"$word\" in the index\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")

=={{header|PowerShell}}==

{{works with|PowerShell|2}}

{

# Create index hashtable, as needed

{

return $WordIndex[$Word]

@'

Files full of

Use the index

to find the files.

Because PowerShell is a shell language, it is "a user interface to do a search". After running the script defining the functions and running a command to index the files, the user can simply run the search function at the PowerShell command prompt.

Alternatively, one could create a more complex custom UI or GUI if desired.

{{out}}

<pre>C:\Test\File1.txt

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>

(formerly Perl 6)

{{works with|rakudo|2015-09-16}}

my %norm;

do for @files -> $file {

}

}

=={{header|REXX}}==

To see more about Burma Shave signs, see the Wikipedia entry: &nbsp; [http://en.wikipedia.org/wiki/Burma-Shave Burma Shave signs.]

@.= /*a dictionary of words (so far). */

!= /*a list of found words (so far). */

q=strip(q, 'T', substr(@punctuation, j, 1) )

end /*j*/

{{out|output|text=&nbsp; when using the default inputs:}}

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

=={{header|Rust}}==

use std::{

Ok(())

{{out}}

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

}

return $files

For the GUI:

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

pack [listbox .files.list -listvariable files]

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

echo >&2

: $((fi += 1))

# search.sh - search an inverted index

}

=={{header|Wren}}==

{{libheader|Wren-pattern}}

{{libheader|Wren-str}}

import "/pattern" for Pattern

import "/str" for Str

if (word == "q" || word == "Q") return

findWord.call(word)

{{out}}