Inverted index: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Phix}}: added syntax colouring, marked p2js incompatible) |
m (→{{header|Wren}}: Minor tidy) |
||
(One intermediate revision by one other user not shown) | |||
Line 15:
{{trans|D}}
<
F parse_file(fname, fcontents)
Line 31:
print(‘'#.' found in #..’.format(w, sorted(Array(index[w]))))
E
print(‘'#.' not found.’.format(w))</
{{out}}
Line 58:
Here is the main program (file inverted_index.adb):
<
use Ada.Text_IO;
Line 171:
end;
end loop;
end Inverted_Index;</
A sample output:
Line 196:
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;
Line 258:
type Storage_Type is new Maps.Map with null record;
end Generic_Inverted_Index;</
Here is the implementation (generic_inverted_index.adb):
<
use Source_Vecs;
Line 356:
end Same_Vector;
end Generic_Inverted_Index;</
===Package Parse_Lines===
Line 362:
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
Line 381:
procedure Iterate_Words(S: String);
end Parse_Lines;</
And here is the implementation (parse_lines.adb):
<
package body Parse_Lines is
Line 426:
end Iterate_Words;
end Parse_Lines;</
===Alternative Implementation of Generic_Inverted_Index (Ada 2012)===
Line 432:
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;
Line 487:
type Storage_Type is new Maps.Map with null record;
end Generic_Inverted_Index;</
The implementation:
<
-- uses some of the new Ada 2012 syntax
use Source_Vecs;
Line 572:
end Same_Vector;
end Generic_Inverted_Index;</
=={{header|AutoHotkey}}==
{{works with|AutoHotkey_L}}
<
inputbox, files, files, file pattern such as c:\files\*.txt
Line 641:
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"
Line 717:
IF C% >= 65 IF C% <= 90 MID$(A$,A%,1) = CHR$(C%+32)
NEXT
= A$</
'''Output:'''
<pre>
Line 728:
=={{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>
Line 878:
search_index(root, "boo");
return 0;
}</
Search for "is": f1.txt other_file source/f2.txt
Search for "banana": other_file
Search for "boo": not found</
=={{header|C sharp|C#}}==
<
using System.Collections.Generic;
using System.IO;
Line 908:
Console.WriteLine("{0} found in: {1}", find, string.Join(" ", Invert(dictionary)[find]));
}
}</
Sample output:
<syntaxhighlight lang="text">files: file1 file2 file3
find: what
what found in: file1 file2</
=={{header|C++}}==
Same idea as the C implementation - trie to store the words
<
#include <algorithm>
#include <fstream>
Line 1,033:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,054:
=={{header|Clojure}}==
<
(:require [clojure.set :as sets]
[clojure.java.io :as io]))
Line 1,079:
(defn search [index query]
(apply sets/intersection (map index (term-seq query))))
</syntaxhighlight>
=={{header|CoffeeScript}}==
<
fs = require 'fs'
Line 1,118:
grep index, 'make_index'
grep index, 'sort'
</syntaxhighlight>
output
<syntaxhighlight lang="text">
> coffee inverted_index.coffee
locations for 'make_index':
Line 1,136:
inverted_index.coffee:35
knuth_sample.coffee:12
</syntaxhighlight>
=={{header|Common Lisp}}==
<
(:use cl))
(in-package rosettacode.inverted-index)
Line 1,174:
:test #'equal))
</syntaxhighlight>
Example:
<
(defparameter *query* "foo bar")
(defparameter *result* (lookup *index* *query*))
(format t "Result for query ~s: ~{~a~^, ~}~%" *query* *result*)</
=={{header|D}}==
<
void main() {
Line 1,214:
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.
Line 1,243:
{{libheader| system.Generics.Collections}}
{{libheader| SYstem.IOUtils}}
<syntaxhighlight lang="delphi">
program Inverted_index;
Line 1,433:
Index.Free;
end.</
Input: Same of [[#D|D]].
{{out}}
Line 1,453:
===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})
Line 1,477:
(let ((text (text-parse text)))
(for ((word text)) (invert-word (string-downcase word) file INVERT))))
</syntaxhighlight>
=== Query ===
Intersect sets values of each word.
<
;; usage : (inverted-search w1 w2 ..)
(define-syntax-rule (inverted-search w ...)
Line 1,493:
(set-intersect res (local-get-value word INVERT)))
FILES words))
</syntaxhighlight>
Output :
<
(map-files invert-text FILES)
(inverted-search is it)
Line 1,505:
(inverted-search boule)
[3]→ null
</syntaxhighlight>
=={{header|Erlang}}==
Line 1,512:
Ditto for any other character.
<syntaxhighlight lang="erlang">
-module( inverted_index ).
Line 1,547:
search_common( Files, Acc ) -> [X || X <- Acc, lists:member(X, Files)].
</syntaxhighlight>
=={{header|F Sharp|F#}}==
<
open System.IO
Line 1,584:
|> Set.intersectMany
printf "Found in: " ; searchResults |> Set.iter (printf "%s ") ; printfn ""</
Sample usage:
<pre>
Line 1,594:
=={{header|Factor}}==
<
sets splitting vectors ;
IN: rosettacode.inverted-index
Line 1,610:
: query ( terms index -- files )
[ at ] curry map [ ] [ intersect ] map-reduce ;
</syntaxhighlight>
Example use :
<syntaxhighlight lang="text">( scratchpad ) { "f1" "f2" "f3" } index-files
--- Data stack:
Line 1,619:
( scratchpad ) { "what" "is" "it" } swap query .
V{ "f1" "f2" }
</syntaxhighlight>
=={{header|Go}}==
<
import (
Line 1,756:
}
}
}</
Session:
<pre>
Line 1,779:
=={{header|Haskell}}==
<
import Data.Char (isAlpha, toLower)
import qualified Data.Map as M
Line 1,810:
intersections xs = foldl1 S.intersection xs
lowercase = map toLower</
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.":
Line 1,821:
The following implements a simple case insensitive inverse index using lists simulating texts.
<
texts := table() # substitute for read and parse files
Line 1,875:
write()
return
end</
Output:<pre>Enter search terms (^z to quit) : is it
Line 1,891:
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
Line 1,909:
return ii
end</
=={{header|J}}==
Line 1,915:
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
Line 1,938:
hits=. buckets{~words i.~.parse tolower y
files {~ >([-.-.)each/hits
)</
Example use:
<
>search 'finally learning'
~help/primer/end.htm
Line 1,950:
~help/primer/gui.htm
>search 'around'
~help/primer/gui.htm</
=={{header|Java}}==
<syntaxhighlight lang="java">
package org.rosettacode;
Line 2,058:
}
</syntaxhighlight>
Example output:
<syntaxhighlight lang="java">
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
Line 2,075:
olympian pg30637.txt
</syntaxhighlight>
=={{header|jq}}==
Line 2,085:
'''Part 1: inverted_index and search'''
<
# construct a lookup table: { word: array_of_docs }
def inverted_index:
Line 2,102:
else reduce words[1:][] as $word
( $dict[words[0]]; overlap( $dict[$word] ) )
end ; </
'''Part 2: Interactive Search'''
Line 2,111:
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 [.]
Line 2,118:
| search($in), prompt_search ) ;
$in | inverted_index | prompt_search</
'''Example''':
<
Enter a string or an array of strings to search for, quoting each string, or 0 to exit:
"is"
Line 2,130:
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
Line 2,169:
const searchterms = ["forehead", "of", "hand", "a", "foot"]
wordsearch(didx, searchterms)
</syntaxhighlight>
=={{header|Kotlin}}==
<
import java.io.File
Line 2,229:
findWord(word)
}
}</
Contents of files:
Line 2,286:
=={{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,
Frame -> All], {s, "tree"}]</
{{out}}
Outputs a graphical user interface with an interactive input field showing filename and the snippet of text that includes the search string.
Line 2,297:
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
Line 2,451:
stdout.write &"... in “{docName}”, line{plural(linenums.len)}"
for num in linenums: stdout.write ' ', num
echo ""</
{{out}}
Line 2,482:
ocamlc -o inv.byte unix.cma bigarray.cma nums.cma -I +sexplib sexplib.cma str.cma inv.cmo
<
type files = string array with sexp
Line 2,562:
| "--index-file", in_file -> index_file in_file
| "--search-word", word -> search_word word
| _ -> usage()</
=={{header|Perl}}==
<
# given an array of files, returns the index
Line 2,618:
# first arg is a comma-separated list of words to search for
print "$_\n"
foreach search_words_with_index({createindex(@ARGV)}, @searchwords);</
=={{header|Phix}}==
Line 2,625:
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>
Line 2,709:
<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.
Line 2,724:
=={{header|PHP}}==
<
function buildInvertedIndex($filenames)
Line 2,769:
echo "Unable to find the word \"$word\" in the index\n";
}
}</
=={{header|PicoLisp}}==
Line 2,782:
it is a banana</pre>
we can read them into a binary tree in the global variable '*MyIndex'
<
(use Word
Line 2,796:
(extract
'((Word) (val (car (idx '*MyIndex Word))))
(rest) ) ) )</
Output:
<pre>: (searchFor "what" "is" "it")
Line 2,809:
=={{header|PowerShell}}==
{{works with|PowerShell|2}}
<
{
# Create index hashtable, as needed
Line 2,851:
{
return $WordIndex[$Word]
}</
<
@'
Files full of
Line 2,866:
Use the index
to find the files.
'@ | Out-File -FilePath C:\Test\File3.txt</
<
Index-File C:\Test\File1.txt, C:\Test\File2.txt, C:\Test\File3.txt</
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.
<
Find-Word files</
{{out}}
<pre>C:\Test\File1.txt
Line 2,882:
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
'''
Line 2,922:
terms = ["what", "is", "it"]
print('\nTerm Search for: ' + repr(terms))
pp(sorted(termsearch(terms)))</
'''Sample Output'''
Line 2,950:
<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>
<
Line 3,001:
print(ans)
ans = Counter(ans)
print(' The phrase is found most commonly in text: ' + repr(ans.most_common(1)[0][0]))</
'''Sample Output'''
Line 3,022:
=={{header|Racket}}==
<
#!/usr/bin/env racket
#lang racket
Line 3,045:
(printf "No matching files.\n")
(printf "Terms found at: ~a.\n" (string-join all ", "))))
</syntaxhighlight>
{{out}}
<pre>
Line 3,064:
(formerly Perl 6)
{{works with|rakudo|2015-09-16}}
<syntaxhighlight lang="raku"
my %norm;
do for @files -> $file {
Line 3,076:
}
}
}</
=={{header|REXX}}==
Line 3,084:
To see more about Burma Shave signs, see the Wikipedia entry: [http://en.wikipedia.org/wiki/Burma-Shave Burma Shave signs.]
<
@.= /*a dictionary of words (so far). */
!= /*a list of found words (so far). */
Line 3,141:
q=strip(q, 'T', substr(@punctuation, j, 1) )
end /*j*/
return q</
{{out|output|text= when using the default inputs:}}
Line 3,240:
'''indexmerge.rb'''
<
@data = Marshal.load open("index.dat")
else
Line 3,268:
open("index.dat", "w") do |index|
index.write Marshal.dump(@data)
end</
'''indexsearch.rb'''
<
@data = Marshal.load open("index.dat")
else
Line 3,292:
end
p @result</
'''Output'''
Line 3,305:
=={{header|Rust}}==
<
use std::{
Line 3,545:
Ok(())
}</
{{out}}
Line 3,580:
=={{header|Scala}}==
<
import java.io.File
Line 3,610:
}
}
}</
{{out}}
<pre>> InvertedIndex "the" file1.txt file2.txt file3.txt
Line 3,632:
=={{header|Tcl}}==
<
proc wordsInString str {
# We define "words" to be "maximal sequences of 'word' characters".
Line 3,720:
}
return $files
}</
For the GUI:
<
pack [labelframe .files -text Files] -side left -fill y
pack [listbox .files.list -listvariable files]
Line 3,756:
lappend found "Searching for files with \"$terms\"" {*}$fs \
"---------------------"
}</
=={{header|TUSCRIPT}}==
<
$$ MODE TUSCRIPT
Line 3,790:
ENDLOOP
PRINT "-> ",files
</syntaxhighlight>
Output:
<pre>
Line 3,807:
{{works with|ksh93}}
<
typeset -A INDEX
Line 3,831:
(( count == $# )) && echo $file
done
}</
Example use:
<
search hello world
</syntaxhighlight>
===Directory on filesystem===
Line 3,846:
* Add note about slowness.
<
# index.sh - create an inverted index
Line 3,894:
echo >&2
: $((fi += 1))
done</
<
# search.sh - search an inverted index
Line 3,928:
}
$want "$@"</
=={{header|Wren}}==
Line 3,935:
{{libheader|Wren-pattern}}
{{libheader|Wren-str}}
<
import "./pattern" for Pattern
import "./str" for Str
import "os" for Process
Line 4,000:
if (word == "q" || word == "Q") return
findWord.call(word)
}</
{{out}}
|