Struct JaccardSearcher

pub struct JaccardSearcher { /* private fields */ }

Searcher for all pairs of similar documents in the Jaccard space.

Approach

The search steps consist of

1. Extracts features from documents, where a feature is a set representation of character or word ngrams.
2. Convert the features into binary sketches through the 1-bit minwise hashing.
3. Search for similar sketches in the Hamming space using ChunkedJoiner.

Examples

use find_simdoc::JaccardSearcher;

let documents = vec![
    "Welcome to Jimbocho, the town of books and curry!",
    "Welcome to Jimbocho, the city of books and curry!",
    "We welcome you to Jimbocho, the town of books and curry.",
    "Welcome to the town of books and curry, Jimbocho!",
];

// Creates a searcher for character trigrams (with random seed value 42).
let searcher = JaccardSearcher::new(3, None, Some(42))
    .unwrap()
    // Builds the database of binary sketches converted from input documents,
    // where binary sketches are in the Hamming space of 20*64 dimensions.
    .build_sketches_in_parallel(documents.iter(), 20)
    .unwrap();

// Searches all similar pairs within radius 0.25.
let results = searcher.search_similar_pairs(0.25);
assert_eq!(results, vec![(0, 1, 0.19375), (0, 2, 0.2125), (0, 3, 0.2328125)]);

Implementations

impl JaccardSearcher

pub fn new( window_size: usize, delimiter: Option<char>, seed: Option<u64>, ) -> Result<Self>

Creates an instance.

Arguments

• window_size - Window size for w-shingling in feature extraction (must be more than 0).
• delimiter - Delimiter for recognizing words as tokens in feature extraction. If None, characters are used for tokens.
• seed - Seed value for random values.

Examples found in repository

examples/find_jaccard.rs (line 12)

fn main() {
    let documents = vec![
        "Welcome to Jimbocho, the town of books and curry!",
        "Welcome to Jimbocho, the city of books and curry!",
        "We welcome you to Jimbocho, the town of books and curry.",
        "Welcome to the town of books and curry, Jimbocho!",
    ];

    // Creates a searcher for character trigrams (with random seed value 42).
    let searcher = JaccardSearcher::new(3, None, Some(42))
        .unwrap()
        // Builds the database of binary sketches converted from input documents,
        // where binary sketches are in the Hamming space of 20*64 dimensions.
        .build_sketches_in_parallel(documents.iter(), 20)
        .unwrap();

    // Searches all similar pairs within radius 0.25.
    let results = searcher.search_similar_pairs(0.25);
    assert_eq!(results, vec![(0, 1, 0.1875), (0, 3, 0.2296875)]);
}

pub const fn shows_progress(self, yes: bool) -> Self

Shows the progress via the standard error output?

pub fn build_sketches<I, D>( self, documents: I, num_chunks: usize, ) -> Result<Self>

where I: IntoIterator<Item = D>, D: AsRef<str>,

Builds the database of sketches from input documents.

Arguments

• documents - List of documents (must not include an empty string).
• num_chunks - Number of chunks of sketches, indicating that the number of dimensions in the Hamming space is num_chunks*64.

pub fn build_sketches_in_parallel<I, D>( self, documents: I, num_chunks: usize, ) -> Result<Self>

where I: Iterator<Item = D> + Send, D: AsRef<str> + Send,

Builds the database of sketches from input documents in parallel.

Arguments

• documents - List of documents (must not include an empty string).
• num_chunks - Number of chunks of sketches, indicating that the number of dimensions in the Hamming space is num_chunks*64.

Notes

The progress is not printed even if shows_progress = true.

Examples found in repository

examples/find_jaccard.rs (line 16)

fn main() {
    let documents = vec![
        "Welcome to Jimbocho, the town of books and curry!",
        "Welcome to Jimbocho, the city of books and curry!",
        "We welcome you to Jimbocho, the town of books and curry.",
        "Welcome to the town of books and curry, Jimbocho!",
    ];

    // Creates a searcher for character trigrams (with random seed value 42).
    let searcher = JaccardSearcher::new(3, None, Some(42))
        .unwrap()
        // Builds the database of binary sketches converted from input documents,
        // where binary sketches are in the Hamming space of 20*64 dimensions.
        .build_sketches_in_parallel(documents.iter(), 20)
        .unwrap();

    // Searches all similar pairs within radius 0.25.
    let results = searcher.search_similar_pairs(0.25);
    assert_eq!(results, vec![(0, 1, 0.1875), (0, 3, 0.2296875)]);
}

pub fn search_similar_pairs(&self, radius: f64) -> Vec<(usize, usize, f64)>

Searches for all pairs of similar documents within an input radius, returning triplets of the left-side id, the right-side id, and their distance.

Examples found in repository

examples/find_jaccard.rs (line 20)

fn main() {
    let documents = vec![
        "Welcome to Jimbocho, the town of books and curry!",
        "Welcome to Jimbocho, the city of books and curry!",
        "We welcome you to Jimbocho, the town of books and curry.",
        "Welcome to the town of books and curry, Jimbocho!",
    ];

    // Creates a searcher for character trigrams (with random seed value 42).
    let searcher = JaccardSearcher::new(3, None, Some(42))
        .unwrap()
        // Builds the database of binary sketches converted from input documents,
        // where binary sketches are in the Hamming space of 20*64 dimensions.
        .build_sketches_in_parallel(documents.iter(), 20)
        .unwrap();

    // Searches all similar pairs within radius 0.25.
    let results = searcher.search_similar_pairs(0.25);
    assert_eq!(results, vec![(0, 1, 0.1875), (0, 3, 0.2296875)]);
}

pub fn len(&self) -> usize

Gets the number of input documents.

pub fn is_empty(&self) -> bool

Checks if the database is empty.

pub fn memory_in_bytes(&self) -> usize

Gets the memory usage in bytes.

pub const fn config(&self) -> &FeatureConfig

Gets the configure of feature extraction.