#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;
#include "bmdbg.h"
static
{
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
;
}
static
{
for (int i = 1; i < argc; ++i)
{
std::string arg = argv[i];
if ((arg == "-h") || (arg == "--help"))
{
return 0;
}
if (arg == "-svout" || arg == "--svout")
{
if (i + 1 < argc)
{
}
else
{
std::cerr << "Error: -svout requires file name" << std::endl;
return 1;
}
continue;
}
if (arg == "-svin" || arg == "--svin")
{
if (i + 1 < argc)
{
}
else
{
std::cerr << "Error: -svin requires file name" << std::endl;
return 1;
}
continue;
}
if (arg == "-idict" || arg == "--idict" )
{
if (i + 1 < argc)
{
}
else
{
std::cerr << "Error: -idict requires file name" << std::endl;
return 1;
}
continue;
}
if (arg == "-remap" || arg == "--remap" || arg == "-r" || arg == "--r")
{
continue;
}
if (arg == "-xor" || arg == "--xor" || arg == "-x" || arg == "--x")
{
continue;
}
if (arg == "-diag" || arg == "--diag" || arg == "-d" || arg == "--d")
{
continue;
}
if (arg == "-timing" || arg == "--timing" || arg == "-t" || arg == "--t")
{
continue;
}
if (arg == "-bench" || arg == "--bench" || arg == "-b" || arg == "--b")
{
continue;
}
std::cerr << "Error: unknown argument: " << arg << std::endl;
return 1;
}
return 0;
}
static
{
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;
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
{
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&)
{
}
if (i % 10000 == 0)
{
cout << "\rReading input file: " << i << flush;
}
}
cout << endl;
return 0;
}
static
{
if (str_vec.size() != str_sv.
size())
throw runtime_error("Error. size() comparison failed!");
string 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!");
}
}
std::cout <<
"Check ok. Dictionary size = " << str_sv.
size() << std:: endl;
}
static
{
std::uniform_int_distribution<unsigned>
rand_dis(0,
unsigned(str_vec.size()-1));
{
unsigned idx;
while (true)
{
continue;
if (idx < str_vec.size())
bench_vec.push_back(str_vec[idx]);
break;
}
{
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');
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)
{
bench_vec_not_found.push_back(str_nf);
break;
}
}
}
}
cout << endl;
}
static
{
cout <<
"Picked " << bench_vec.
size() <<
" / "
<< bench_vec_not_found.size() << " samples. Running benchmarks."
<< endl;
unsigned bench_size = unsigned(bench_vec.size());
{
{
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));
}
}
}
{
for (const string& term : bench_vec_not_found)
{
auto p = std::lower_bound(str_vec.begin(), str_vec.end(), term);
}
}
}
{
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 (const string& term : bench_vec)
{
auto it = str_map.find(term);
if (it != str_map.end())
{
bv2.
set(
unsigned(it->second));
}
}
}
{
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 (const string& term : bench_vec)
{
unsigned pos;
bool found = scanner.
find_eq_str(str_sv, term.c_str(), pos);
if (found)
{
}
}
}
{
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;
}
}
}
}
{
scanner.
bind(str_sv,
true);
{
for (const string& term : bench_vec)
{
unsigned pos;
if (found)
{
}
}
}
{
for (const string& term : bench_vec_not_found)
{
unsigned pos;
if (found)
{
cerr << "scanner empty search returned value..." << endl;
}
}
}
}
if (cmp != 0)
throw runtime_error("Error. RB-search mismatch!");
if (cmp != 0)
throw runtime_error("Error. scanner mismatch!");
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)
{
return 1;
}
try
{
if (ret != 0)
{
return ret;
}
{
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())
{
{
for (const string& term : str_vec)
bi = term;
}
{
str_sv.
swap(str_sv_remap);
}
}
{
{
}
{
cout << "Input vector empty!" << endl;
exit(1);
}
if (str_vec.empty())
{
{
string s;
str_vec.emplace_back(std::move(s));
}
}
}
{
bool eq = str_sv.
equal(str_sv_control);
if (!eq)
{
cerr << "Serialization control failed" << endl;
assert(0); exit(1);
}
}
{
{
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;
cout << "Ok" << endl;
}
}
{
}
{
std::cout << std::endl << "Performance:" << std::endl;
}
}
catch (std::exception& ex)
{
std::cerr << "Error:" << ex.what() << std::endl;
return 1;
}
return 0;
}
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
#define BM_DECLARE_TEMP_BLOCK(x)
Algorithms for bvector<> (main include)
Generation of random subset.
Serialization / compression of bvector<>. Set theoretical operations on compressed BLOBs.
Algorithms for bm::sparse_vector.
Serialization for sparse_vector<>
string sparse vector based on bit-transposed matrix
Timing utilities for benchmarking (internal)
pre-processor un-defines to avoid global space pollution (internal)
Bitvector Bit-vector container with runtime compression of bits.
bool test(size_type n) const BMNOEXCEPT
returns true if bit n is set and false is bit n is 0.
size_type size() const BMNOEXCEPT
Returns bvector's capacity (number of bits it can store)
size_type count() const BMNOEXCEPT
population count (count of ON bits)
bvector< Alloc > & set(size_type n, bool val=true)
Sets bit n if val is true, clears bit n if val is false.
void resize(size_type new_size)
Change size of the bvector.
int compare(const bvector< Alloc > &bvect) const BMNOEXCEPT
Lexicographical comparison with a bitvector.
Utility class to collect performance measurements and statistics.
std::map< std::string, statistics > duration_map_type
test name to duration map
static void print_duration_map(TOut &tout, const duration_map_type &dmap, format fmt=ct_time)
algorithms for sparse_vector scan/search
bool bfind_eq_str(const SV &sv, const value_type *str, size_type &pos)
binary find first sparse vector element (string) Sparse vector must be sorted.
void bind(const SV &sv, bool sorted)
bind sparse vector for all searches
bool find_eq_str(const SV &sv, const value_type *str, bvector_type &bv_out)
find sparse vector elements (string)
void flush()
flush the accumulated buffer.
succinct sparse vector for strings with compression using bit-slicing ( transposition) method
void swap(str_sparse_vector &str_sv) BMNOEXCEPT
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
bool empty() const
return true if vector is empty
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
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...
size_type size() const
return size of the vector
size_type get(size_type idx, value_type *str, size_type buf_size) const BMNOEXCEPT
get specified element
back_insert_iterator get_back_inserter()
Provide back insert iterator Back insert iterator implements buffered insertion, which is faster,...
bvector_type::size_type size_type
std::random_device rand_dev
std::uniform_int_distribution rand_dis(1, int(vector_max))
std::mt19937 gen(rand_dev())
int main(int argc, char *argv[])
static int parse_args(int argc, char *argv[])
static void show_help()
Print help.
vector< string > string_vector
bm::chrono_taker ::duration_map_type timing_map
static int load_dict_report(const std::string &fname, string_vector &str_vec)
Parse the input file and extract dictionary values.
static void run_benchmark(const str_sparse_vect &str_sv, const string_vector &str_vec)
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.
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.
const unsigned benchmark_max
bm::str_sparse_vector< char, bm::bvector<>, 64 > str_sparse_vect