Rebol3 Code Examplex


Inverted index

Store terms and the documents or positions where they appear, making text search fast and efficient.

Rebol [
    title: "Rosetta code: Inverted index"
    file:  %Inverted_index.r3
    url:   https://rosettacode.org/wiki/Inverted_index
]

word-search: context [
    indexes: make map! []
    ;; Using simplified word delimiters
    word-chars: complement charset { ^-^/^M.!?,;:'"()-[]{}—}
    make-index: function [
        {Build a word->positions map from a string.}
        file [file!] text [string! none!]
    ][
        unless text [text: read/string file]
        index: make map! []
        print ["Indexing file:" as-yellow file]
        parse text [
            any [
                ;; capture word and its position
                pos: copy word: some word-chars (
                    append any [
                        index/:word
                        index/:word: copy [] ;; init new entry if needed
                    ] index? pos
                )
                | to word-chars              ;; skip delimiters
            ]
        ]
        indexes/:file: index
    ]
    find: function [word [string!]][
        print ["Searching for:" as-green word]
        count: 0
        foreach [file index] indexes [
            if positions: index/:word [
                print [tab "in" as-yellow file "at positions:" ajoin/with positions ", "]
                count: count + length? positions
            ]
        ]
        print either/only zero? count [
            tab "not found!"
        ][  tab "found in" count "positions."]
    ]
]

;; Build per-file indexes
foreach [file str][
    %inv1.txt {It is what it is.}
    %inv2.txt {What is it?}
    %inv3.txt {It is a banana!}
][  word-search/make-index file str ]

print ""
;; Search for some words
foreach word [
    "cat" "is" "banana" "it" "what" "a"
][
    word-search/find word
]

Output:

Indexing file: inv1.txt
Indexing file: inv2.txt
Indexing file: inv3.txt

Searching for: cat
     not found!
Searching for: is
     in inv1.txt at positions: 4, 15
     in inv2.txt at positions: 6
     in inv3.txt at positions: 4
     found in 4 positions.
Searching for: banana
     in inv3.txt at positions: 9
     found in 1 positions.
Searching for: it
     in inv1.txt at positions: 1, 12
     in inv2.txt at positions: 9
     in inv3.txt at positions: 1
     found in 4 positions.
Searching for: what
     in inv1.txt at positions: 7
     in inv2.txt at positions: 1
     found in 2 positions.
Searching for: a
     in inv3.txt at positions: 7
     found in 1 positions.