xsample05.cpp
/*
Copyright(c) 2018 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
For more information please visit: http://bitmagic.io
*/
/** \example xsample05.cpp
*/
/*! \file xsample05.cpp
\brief Example: Example on how to use bit-transposed string sparse vector
Illustrates how to build a sparse vector, serialize it to disk,
load back and do search or binary hybrid search.
\sa bm::str_sparse_vector<>
*/
#include <iostream>
#include <sstream>
#include <chrono>
#include <regex>
#include <time.h>
#include <stdio.h>
#include <vector>
#include <map>
#include <chrono>
#include <map>
#include <utility>
#include <algorithm>
#include <random>
using namespace std;
//#define BMAVX2OPT
#include "bm.h"
#include "bmalgo.h"
#include "bmserial.h"
#include "bmrandom.h"
#include "bmstrsparsevec.h"
#include "bmsparsevec_algo.h"
#include "bmsparsevec_serial.h"
#include "bmalgo_similarity.h"
#include "bmsparsevec_util.h"
#include "bmdbg.h"
#include "bmtimer.h"
#include "bmundef.h" /* clear the pre-proc defines from BM */
/// Print help
static
void show_help()
{
std::cerr
<< "BitMagic Dictionary Search Sample (c) 2018" << std::endl
<< "-idict file-name -- input set file to parse" << std::endl
<< "-svout spase vector output -- sparse vector name to save" << std::endl
<< "-svin sparse vector input -- sparse vector file name to load " << std::endl
<< "-remap -- re-mapping of string characters " << std::endl
<< "-xor -- use XOR compression filtering" << std::endl
<< "-diag -- run diagnostics" << std::endl
<< "-bench -- run benchmarks" << std::endl
<< "-timing -- collect timings" << std::endl
;
}
// Arguments
//
std::string sv_out_name;
std::string sv_in_name;
std::string i_name;
bool is_diag = false;
bool is_timing = false;
bool is_bench = false;
bool is_remap = false;
bool is_xor = false;
// Parse command line arguments
static
int parse_args(int argc, char *argv[])
{
for (int i = 1; i < argc; ++i)
{
std::string arg = argv[i];
if ((arg == "-h") || (arg == "--help"))
{
show_help();
return 0;
}
if (arg == "-svout" || arg == "--svout")
{
if (i + 1 < argc)
{
sv_out_name = argv[++i];
}
else
{
std::cerr << "Error: -svout requires file name" << std::endl;
return 1;
}
continue;
}
if (arg == "-svin" || arg == "--svin")
{
if (i + 1 < argc)
{
sv_in_name = argv[++i];
}
else
{
std::cerr << "Error: -svin requires file name" << std::endl;
return 1;
}
continue;
}
if (arg == "-idict" || arg == "--idict" )
{
if (i + 1 < argc)
{
i_name = argv[++i];
}
else
{
std::cerr << "Error: -idict requires file name" << std::endl;
return 1;
}
continue;
}
if (arg == "-remap" || arg == "--remap" || arg == "-r" || arg == "--r")
{
is_remap = true;
continue;
}
if (arg == "-xor" || arg == "--xor" || arg == "-x" || arg == "--x")
{
is_xor = true;
continue;
}
if (arg == "-diag" || arg == "--diag" || arg == "-d" || arg == "--d")
{
is_diag = true;
continue;
}
if (arg == "-timing" || arg == "--timing" || arg == "-t" || arg == "--t")
{
is_timing = true;
continue;
}
if (arg == "-bench" || arg == "--bench" || arg == "-b" || arg == "--b")
{
is_bench = true;
continue;
}
std::cerr << "Error: unknown argument: " << arg << std::endl;
return 1;
} // for i
return 0;
}
// Global types
//
typedef bm::str_sparse_vector<char, bm::bvector<>, 64> str_sparse_vect;
typedef vector<string> string_vector;
bm::chrono_taker<>::duration_map_type timing_map;
/// Parse the input file and extract dictionary values.
///
static
int load_dict_report(const std::string& fname, string_vector& str_vec)
{
bm::chrono_taker tt1(cout, "1. parse input data ", 1, &timing_map);
std::ifstream fin(fname.c_str(), std::ios::in);
if (!fin.good())
return -1;
std::string line;
std::regex reg("[|]");
std::sregex_token_iterator it_end;
string trim_chars("\" ");
for (unsigned i = 0; std::getline(fin, line); ++i)
{
if (line.empty() || !isdigit(line.front()))
continue;
// regex based tokenizer
std::sregex_token_iterator it(line.begin(), line.end(), reg, -1);
std::vector<std::string> line_vec(it, it_end);
if (line_vec.empty())
continue;
try
{
// trip the extra chars
string& col13 = line_vec.at(13);
col13.erase(0, col13.find_first_not_of(trim_chars));
col13.erase(col13.find_last_not_of(trim_chars) + 1);
if (!col13.empty())
str_vec.emplace_back(col13);
}
catch (std::exception&)
{
// just ignore (not ideal, but ok for a sketch ETL)
}
if (i % 10000 == 0)
{
cout << "\rReading input file: " << i << flush;
}
} // for
cout << endl;
return 0;
}
/// Compare STL vector with bit-transposed container to check correctness
///
static
void check_sparse(const str_sparse_vect& str_sv, const string_vector& str_vec)
{
if (str_vec.size() != str_sv.size())
throw runtime_error("Error. size() comparison failed!");
string s;
for (str_sparse_vect::size_type i = 0; i < str_sv.size(); ++i)
{
str_sv.get(i, s);
const string& s_control = str_vec[i];
if (s != s_control)
{
cout << "idx=" << i << s << "!=" << s_control << endl;
throw runtime_error("Error. element comparison failed!");
}
} // for
std::cout << "Check ok. Dictionary size = " << str_sv.size() << std:: endl;
}
const unsigned benchmark_max = 50000; // benchmark sampling size
/// Sample a few random terms out of collection
static
void pick_benchmark_set(string_vector& bench_vec, string_vector& bench_vec_not_found, const string_vector& str_vec)
{
std::random_device rand_dev;
std::mt19937 gen(rand_dev()); // mersenne_twister_engine
std::uniform_int_distribution<unsigned> rand_dis(0, unsigned(str_vec.size()-1)); // generate uniform numebrs for [1, vector_max]
bm::bvector<> bv;
bench_vec.resize(0);
for (unsigned i = 0; i < benchmark_max; ++i)
{
unsigned idx;
while (true)
{
idx = unsigned(rand_dis(gen));
if (bv.test(idx)) // make sure benchmark example is not repeated
continue;
if (idx < str_vec.size())
bench_vec.push_back(str_vec[idx]);
break;
}
bv.set(idx); // mark as set
// generate not-found case by modifying a letter in an existing sample
{
string str_nf = str_vec[idx];
string::reverse_iterator rit = str_nf.rbegin();
string::reverse_iterator rit_end = str_nf.rend();
for (; rit != rit_end; ++rit)
{
char ch = *rit;
int a = rand() % 26 + int('A'); // generate random letter
ch = char(a);
*rit = ch;
auto it = std::lower_bound(str_vec.begin(), str_vec.end(), str_nf);
if (it == str_vec.end() || *it != str_nf) // check if not found
{
bench_vec_not_found.push_back(str_nf);
break;
}
} // for rit
}
} // for
cout << endl;
}
static
void run_benchmark(const str_sparse_vect& str_sv, const string_vector& str_vec)
{
string_vector bench_vec;
string_vector bench_vec_not_found; // vector for impossible dictionary items
pick_benchmark_set(bench_vec, bench_vec_not_found, str_vec);
bm::bvector<> bv1, bv2, bv3, bv4;
cout << "Picked " << bench_vec.size() << " / "
<< bench_vec_not_found.size() << " samples. Running benchmarks."
<< endl;
unsigned bench_size = unsigned(bench_vec.size());
{
{
bm::chrono_taker tt1(cout, "3. std::lower_bound() search", bench_size, &timing_map);
for (const string& term : bench_vec)
{
auto it = std::lower_bound(str_vec.begin(), str_vec.end(), term);
if (it != str_vec.end())
{
string_vector::size_type idx =
string_vector::size_type(std::distance(str_vec.begin(), it));
bv1.set(unsigned(idx));
}
} // for
}
{
bm::chrono_taker tt2(cout, "3a. std::lower_bound() search (empty)", bench_size, &timing_map);
for (const string& term : bench_vec_not_found)
{
auto p = std::lower_bound(str_vec.begin(), str_vec.end(), term);
(void) p;
} // for
}
}
{
// construct std::map<> (RB-tree)
std::map<string, unsigned> str_map;
for (string_vector::size_type i = 0; i < str_vec.size(); ++i)
{
const string& s = str_vec[i];
str_map[s] = unsigned(i);
} // for
{
bm::chrono_taker tt1(cout, "4. std::map<> search", bench_size, &timing_map);
for (const string& term : bench_vec)
{
auto it = str_map.find(term);
if (it != str_map.end())
{
bv2.set(unsigned(it->second));
}
} // for
}
{
bm::chrono_taker tt2(cout, "4a. std::map<> search (empty)", bench_size, &timing_map);
for (const string& term : bench_vec_not_found)
{
auto it = str_map.find(term);
if (it != str_map.end())
{
cerr << "empty search returned value..." << endl;
}
} // for
}
}
{
bm::sparse_vector_scanner<str_sparse_vect> scanner;
{
bm::chrono_taker tt1(cout, "5. bm::sparse_vector_scanner<> search", bench_size, &timing_map);
for (const string& term : bench_vec)
{
unsigned pos;
bool found = scanner.find_eq_str(str_sv, term.c_str(), pos);
if (found)
{
bv3.set(pos);
}
} // for
}
{
bm::chrono_taker tt1(cout, "5a. bm::sparse_vector_scanner<> search (empty)", bench_size, &timing_map);
for (const string& term : bench_vec_not_found)
{
unsigned pos;
bool found = scanner.find_eq_str(str_sv, term.c_str(), pos);
if (found)
{
cerr << "scanner empty search returned value..." << endl;
}
} // for
}
}
{
bm::sparse_vector_scanner<str_sparse_vect> scanner;
scanner.bind(str_sv, true); // attach SV as permanent search parameter to share cached values
{
bm::chrono_taker tt1(cout, "6. bm::sparse_vector_scanner<> binary search", bench_size, &timing_map);
for (const string& term : bench_vec)
{
unsigned pos;
bool found = scanner.bfind_eq_str(term.c_str(), pos);
if (found)
{
bv4.set(pos);
}
} // for
}
{
bm::chrono_taker tt2(cout, "6a. bm::sparse_vector_scanner<> binary search (empty)", bench_size, &timing_map);
for (const string& term : bench_vec_not_found)
{
unsigned pos;
bool found = scanner.bfind_eq_str(term.c_str(), pos);
if (found)
{
cerr << "scanner empty search returned value..." << endl;
}
} // for
}
}
// various integrity checks
//
int cmp = bv1.compare(bv2);
if (cmp != 0)
throw runtime_error("Error. RB-search mismatch!");
cmp = bv1.compare(bv3);
if (cmp != 0)
throw runtime_error("Error. scanner mismatch!");
cmp = bv1.compare(bv4);
if (cmp != 0)
throw runtime_error("Error. binary scanner mismatch!");
if (bv1.count() != bench_size)
throw runtime_error("Error. Search result missing elements!");
}
int main(int argc, char *argv[])
{
if (argc < 3)
{
show_help();
return 1;
}
string_vector str_vec; // dictionary vector (STL)
str_sparse_vect str_sv; // bit-transposed sparse vector
try
{
auto ret = parse_args(argc, argv);
if (ret != 0)
{
return ret;
}
if (!i_name.empty())
{
auto res = load_dict_report(i_name, str_vec);
if (res != 0)
{
return res;
}
cout << "Loaded " << str_vec.size() << " dictionary names." << endl;
std::sort(str_vec.begin(), str_vec.end());
}
if (str_vec.size()) // load the sparse vector
{
bm::chrono_taker tt1(cout, "2. build sparse vector", 1, &timing_map);
{
// use insert iterator to load vector (faster than push-back)
//
auto bi = str_sv.get_back_inserter();
for (const string& term : str_vec)
bi = term;
bi.flush();
}
// build remapped (dense) succinct vector
// (this should be final), no more edits in this form
if (is_remap)
{
str_sparse_vect str_sv_remap;
str_sv_remap.remap_from(str_sv);
str_sv.swap(str_sv_remap);
}
BM_DECLARE_TEMP_BLOCK(tb)
str_sv.optimize(tb); // memory optimization after load
}
if (!sv_in_name.empty())
{
{
bm::chrono_taker tt1(cout, "8. Load sparse vector", 1, &timing_map);
file_load_svector(str_sv, sv_in_name);
}
if (str_sv.empty())
{
cout << "Input vector empty!" << endl;
exit(1);
}
if (str_vec.empty())
{
for (str_sparse_vect::size_type i = 0; i < str_sv.size(); ++i)
{
string s;
str_sv.get(i, s);
str_vec.emplace_back(std::move(s));
} // for
}
}
// save SV vector to file
if (!sv_out_name.empty() && !str_sv.empty())
{
bm::chrono_taker tt1(cout, "7. Save sparse vector", 1, &timing_map);
file_save_svector(str_sv, sv_out_name, 0, is_xor);
str_sparse_vect str_sv_control;
file_load_svector(str_sv_control, sv_out_name);
bool eq = str_sv.equal(str_sv_control);
if (!eq)
{
cerr << "Serialization control failed" << endl;
assert(0); exit(1);
}
}
if (is_diag)
{
if (!str_sv.empty())
{
print_svector_stat(cout,str_sv, false);
}
if (str_vec.size())
{
size_t total_size = 0;
for (const string& term : str_vec)
{
total_size += term.size();
}
cout << "String dictionary size: "
<< total_size / 1024 << "KB (" << total_size / (1024*1024) << "MB)"
<< endl;
}
if (str_sv.size() && str_vec.size())
{
cout << "Run full comparison check..." << endl;
check_sparse(str_sv, str_vec); // run a paranoiya check
cout << "Ok" << endl;
}
}
if (is_bench) // run set of benchmarks
{
run_benchmark(str_sv, str_vec);
}
if (is_timing) // print all collected timings
{
std::cout << std::endl << "Performance:" << std::endl;
bm::chrono_taker<>::print_duration_map(cout, timing_map, bm::chrono_taker<>::ct_time);
}
}
catch (std::exception& ex)
{
std::cerr << "Error:" << ex.what() << std::endl;
return 1;
}
return 0;
}
bm.h
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
BM_DECLARE_TEMP_BLOCK
#define BM_DECLARE_TEMP_BLOCK(x)
Definition bm.h:47
bmalgo.h
Algorithms for bvector<> (main include).
bmalgo_similarity.h
bmrandom.h
Generation of random subset.
bmserial.h
Serialization / compression of bvector<>. Set theoretical operations on compressed BLOBs.
bmsparsevec_algo.h
Algorithms for bm::sparse_vector.
bmsparsevec_serial.h
Serialization for sparse_vector<>.
bmsparsevec_util.h
bmstrsparsevec.h
string sparse vector based on bit-transposed matrix
bmtimer.h
Timing utilities for benchmarking (internal).
bmundef.h
pre-processor un-defines to avoid global space pollution (internal)
bm::bvector
Bitvector Bit-vector container with runtime compression of bits.
Definition bm.h:115
bm::bvector::test
bool test(size_type n) const BMNOEXCEPT
returns true if bit n is set and false is bit n is 0.
Definition bm.h:1502
bm::bvector::size
size_type size() const BMNOEXCEPT
Returns bvector's capacity (number of bits it can store).
Definition bm.h:1300
bm::bvector::count
size_type count() const BMNOEXCEPT
population count (count of ON bits)
Definition bm.h:2401
bm::bvector::set
bvector< Alloc > & set(size_type n, bool val=true)
Sets bit n if val is true, clears bit n if val is false.
Definition bm.h:4188
bm::bvector::resize
void resize(size_type new_size)
Change size of the bvector.
Definition bm.h:2463
bm::bvector::compare
int compare(const bvector< Alloc > &bvect) const BMNOEXCEPT
Lexicographical comparison with a bitvector.
Definition bm.h:3744
bm::chrono_taker
Utility class to collect performance measurements and statistics.
Definition bmtimer.h:41
bm::chrono_taker::duration_map_type
std::map< std::string, statistics > duration_map_type
test name to duration map
Definition bmtimer.h:66
bm::chrono_taker::ct_time
@ ct_time
Definition bmtimer.h:59
bm::chrono_taker::print_duration_map
static void print_duration_map(TOut &tout, const duration_map_type &dmap, format fmt=ct_time)
Definition bmtimer.h:150
bm::sparse_vector_scanner
algorithms for sparse_vector scan/search
Definition bmsparsevec_algo.h:582
bm::sparse_vector_scanner::bind
void bind(const SV &sv, bool sorted)
bind sparse vector for all searches
Definition bmsparsevec_algo.h:1594
bm::sparse_vector_scanner::bfind_eq_str
bool bfind_eq_str(const SV &sv, const value_type *str, size_type &pos)
binary find first sparse vector element (string).
Definition bmsparsevec_algo.h:2638
bm::sparse_vector_scanner::find_eq_str
bool find_eq_str(const SV &sv, const value_type *str, bvector_type &bv_out)
find sparse vector elements (string)
bm::str_sparse_vector
succinct sparse vector for strings with compression using bit-slicing ( transposition) method
Definition bmstrsparsevec.h:72
bm::str_sparse_vector::optimize
void optimize(bm::word_t *temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, typename str_sparse_vector< CharType, BV, STR_SIZE >::statistics *stat=0)
run memory optimization for all vector planes
Definition bmstrsparsevec.h:1848
bm::str_sparse_vector::empty
bool empty() const
return true if vector is empty
Definition bmstrsparsevec.h:862
bm::str_sparse_vector::equal
bool equal(const str_sparse_vector< CharType, BV, STR_SIZE > &sv, bm::null_support null_able=bm::use_null) const BMNOEXCEPT
check if another sparse vector has the same content and size
Definition bmstrsparsevec.h:2493
bm::str_sparse_vector::remap_from
void remap_from(const str_sparse_vector &str_sv, octet_freq_matrix_type *omatrix=0)
Build remapping profile and load content from another sparse vector Remapped vector likely saves memo...
Definition bmstrsparsevec.h:2389
bm::str_sparse_vector::size
size_type size() const
return size of the vector
Definition bmstrsparsevec.h:857
bm::str_sparse_vector::get
size_type get(size_type idx, value_type *str, size_type buf_size) const BMNOEXCEPT
get specified element
Definition bmstrsparsevec.h:1827
bm::str_sparse_vector::get_back_inserter
back_insert_iterator get_back_inserter()
Provide back insert iterator Back insert iterator implements buffered insertion, which is faster,...
Definition bmstrsparsevec.h:958
bm::str_sparse_vector::swap
void swap(size_type idx1, size_type idx2)
swap two vector elements between each other
Definition bmstrsparsevec.h:1693
bm::str_sparse_vector< char, bm::bvector<>, 64 >::size_type
bvector_type::size_type size_type
Definition bmstrsparsevec.h:79
rand_dev
std::random_device rand_dev
Definition sample11.cpp:51
rand_dis
std::uniform_int_distribution rand_dis(1, int(vector_max))
timing_map
bm::chrono_taker ::duration_map_type timing_map
Definition sample11.cpp:46
gen
std::mt19937 gen(rand_dev())
main
int main(void)
Definition sample1.cpp:43
parse_args
static int parse_args(int argc, char *argv[])
Definition xsample03.cpp:110
is_bench
bool is_bench
Definition xsample03.cpp:107
sv_in_name
std::string sv_in_name
Definition xsample03.cpp:102
show_help
static void show_help()
Definition xsample03.cpp:81
is_diag
bool is_diag
Definition xsample03.cpp:105
sv_out_name
std::string sv_out_name
Definition xsample03.cpp:100
run_benchmark
static void run_benchmark(const sparse_vector_u32 &sv, const rsc_sparse_vector_u32 &csv)
Definition xsample03.cpp:349
is_timing
bool is_timing
Definition xsample03.cpp:106
string_vector
vector< string > string_vector
Definition xsample05.cpp:189
load_dict_report
static int load_dict_report(const std::string &fname, string_vector &str_vec)
Parse the input file and extract dictionary values.
Definition xsample05.cpp:198
pick_benchmark_set
static void pick_benchmark_set(string_vector &bench_vec, string_vector &bench_vec_not_found, const string_vector &str_vec)
Sample a few random terms out of collection.
Definition xsample05.cpp:270
check_sparse
static void check_sparse(const str_sparse_vect &str_sv, const string_vector &str_vec)
Compare STL vector with bit-transposed container to check correctness.
Definition xsample05.cpp:248
is_xor
bool is_xor
Definition xsample05.cpp:94
i_name
std::string i_name
Definition xsample05.cpp:89
benchmark_max
const unsigned benchmark_max
Definition xsample05.cpp:266
is_remap
bool is_remap
Definition xsample05.cpp:93
str_sparse_vect
bm::str_sparse_vector< char, bm::bvector<>, 64 > str_sparse_vect
Definition xsample05.cpp:188