<commit_before>#pragma once
/**
	@file
	@brief FM-index
	@author <NAME>(@herumi)
	@license modified new BSD license
	http://opensource.org/licenses/BSD-3-Clause
*/
#include <map>
#include <vector>
#include <fstream>
#include <stdio.h>
#include <cybozu/wavelet_matrix.hpp>
#include <cybozu/frequency.hpp>

#ifdef _MSC_VER
#pragma warning(push)
#pragma warning(disable:4244)
#pragma warning(disable:4389)
#pragma warning(disable:4018)
#endif
#include "sais.hxx"
#ifdef _MSC_VER
#pragma warning(pop)
#endif

#ifdef _MSC_VER
#pragma warning(push)
#pragma warning(disable:4127) // constant condition
#endif

namespace cybozu {
/*
	T : type of alphabet
	isRawData : deal with input data as is
	T must be uint8_t or uint16_t if isRawData
*/
template<class T, bool isRawData = false>
class FMindexT {
public:
	static const size_t maxCharNum = size_t(1) << (sizeof(T) * 8);
	typedef std::vector<uint32_t> Vec32;
	typedef std::vector<T> Vec;
	typedef cybozu::WaveletMatrixT<false> WaveletMatrix;
	typedef cybozu::SucVectorT<uint32_t, false> SucVector;
	Vec32 cf;
	WaveletMatrix wm;
	Vec32 alignedSa;
	SucVector alignedPos;
	cybozu::Frequency<T, uint32_t> freq;
	int skip_;
	size_t charNum_;

	/*
		setup freq, cf by [begin, end)
	*/
	template<class Iter>
	void initCf(Vec& v, Iter begin, Iter end)
	{
		const size_t size = std::distance(begin, end);
		if (size >= (uint64_t(1) << 32) - 1) {
			throw cybozu::Exception("FMindexT:initCf:too large dataSize") << size;
		}
		v.resize(size + 1); // add NUL at the end of data
		if (isRawData) {
			assert(sizeof(T) <= 16);
			charNum_ = size_t(1) << (sizeof(T) * 8);
			std::vector<uint32_t> charNumTbl(charNum_);
			charNumTbl[0] = 1;
			for (size_t i = 0; i < size; i++) {
				T c = *begin++;
				if (c <= 0) throw cybozu::Exception("FMindext:initCf:zero alphabet") << c;
				v[i] = c;
				charNumTbl[c]++;
			}
			cf.resize(charNum_);
			uint32_t sum = 0;
			for (size_t i = 0; i < charNum_; i++) {
				cf[i] = sum;
				sum += charNumTbl[i];
			}
		} else {
			freq.init(begin, end);
			charNum_ = freq.size() + 1; // +1 means last zero
			if (charNum_ > maxCharNum) throw cybozu::Exception("FMindexT:initCf:too many alphabet");
			for (size_t i = 0; i < size; i++) {
				v[i] = static_cast<T>(freq.getIndex(*begin++) + 1);
			}
			cf.resize(charNum_);
			cf[0] = 0;
			uint32_t sum = 1;
			for (size_t i = 1; i < charNum_; i++) {
				cf[i] = sum;
				sum += freq.getFrequency(freq.getElement(i - 1));
			}
		}
	}
	void initBwt(Vec& bwt, const Vec& s, const Vec32& sa) const
	{
		const size_t size = sa.size();
		bwt.resize(size);
		for (size_t i = 0; i < size; i++) {
			if (sa[i] > 0) {
				bwt[i] = s[sa[i] - 1];
			} else {
				bwt[i] = s[size - 1];
			}
		}
	}
	size_t getBitLen(size_t x) const
	{
		if (x == 0) return 1;
		size_t ret = 0;
		while (x > 0) {
			x >>= 1;
			ret++;
		}
		return ret;
	}
public:
	FMindexT()
		: skip_(4)
		, charNum_(0)
	{
	}

	/*
		[begin, end)
		replace '\0' in [begin, end) with space
		append '\0' at the end of [begin, end)
	*/
	template<class Iter>
	void init(Iter begin, Iter end, int skip = 8)
	{
		if (skip <= 0) {
			throw cybozu::Exception("FMindexT:buildFMindex:skip is positive") << skip;
		}
		skip_ = skip;
		Vec v;
		initCf(v, begin, end);
		const size_t dataSize = v.size();

		Vec32 sa;
		sa.resize(dataSize);
		if (saisxx(&v[0], &sa[0], (int)dataSize, (int)charNum_) == -1) {
			throw cybozu::Exception("FMindexT:init:saisxx");
		}
		Vec bwt;
		initBwt(bwt, v, sa);
		wm.init(bwt, getBitLen(charNum_));

		alignedPos.resize(dataSize);
		for (size_t i = 0; i < dataSize; i++) {<commit_msg>fix default skip<commit_after>#pragma once
/**
	@file
	@brief FM-index
	@author <NAME>(@herumi)
	@license modified new BSD license
	http://opensource.org/licenses/BSD-3-Clause
*/
#include <map>
#include <vector>
#include <fstream>
#include <stdio.h>
#include <cybozu/wavelet_matrix.hpp>
#include <cybozu/frequency.hpp>

#ifdef _MSC_VER
#pragma warning(push)
#pragma warning(disable:4244)
#pragma warning(disable:4389)
#pragma warning(disable:4018)
#endif
#include "sais.hxx"
#ifdef _MSC_VER
#pragma warning(pop)
#endif

#ifdef _MSC_VER
#pragma warning(push)
#pragma warning(disable:4127) // constant condition
#endif

namespace cybozu {
/*
	T : type of alphabet
	isRawData : deal with input data as is
	T must be uint8_t or uint16_t if isRawData
*/
template<class T, bool isRawData = false>
class FMindexT {
public:
	static const size_t maxCharNum = size_t(1) << (sizeof(T) * 8);
	typedef std::vector<uint32_t> Vec32;
	typedef std::vector<T> Vec;
	typedef cybozu::WaveletMatrixT<false> WaveletMatrix;
	typedef cybozu::SucVectorT<uint32_t, false> SucVector;
	Vec32 cf;
	WaveletMatrix wm;
	Vec32 alignedSa;
	SucVector alignedPos;
	cybozu::Frequency<T, uint32_t> freq;
	int skip_;
	size_t charNum_;

	/*
		setup freq, cf by [begin, end)
	*/
	template<class Iter>
	void initCf(Vec& v, Iter begin, Iter end)
	{
		const size_t size = std::distance(begin, end);
		if (size >= (uint64_t(1) << 32) - 1) {
			throw cybozu::Exception("FMindexT:initCf:too large dataSize") << size;
		}
		v.resize(size + 1); // add NUL at the end of data
		if (isRawData) {
			assert(sizeof(T) <= 16);
			charNum_ = size_t(1) << (sizeof(T) * 8);
			std::vector<uint32_t> charNumTbl(charNum_);
			charNumTbl[0] = 1;
			for (size_t i = 0; i < size; i++) {
				T c = *begin++;
				if (c <= 0) throw cybozu::Exception("FMindext:initCf:zero alphabet") << c;
				v[i] = c;
				charNumTbl[c]++;
			}
			cf.resize(charNum_);
			uint32_t sum = 0;
			for (size_t i = 0; i < charNum_; i++) {
				cf[i] = sum;
				sum += charNumTbl[i];
			}
		} else {
			freq.init(begin, end);
			charNum_ = freq.size() + 1; // +1 means last zero
			if (charNum_ > maxCharNum) throw cybozu::Exception("FMindexT:initCf:too many alphabet");
			for (size_t i = 0; i < size; i++) {
				v[i] = static_cast<T>(freq.getIndex(*begin++) + 1);
			}
			cf.resize(charNum_);
			cf[0] = 0;
			uint32_t sum = 1;
			for (size_t i = 1; i < charNum_; i++) {
				cf[i] = sum;
				sum += freq.getFrequency(freq.getElement(i - 1));
			}
		}
	}
	void initBwt(Vec& bwt, const Vec& s, const Vec32& sa) const
	{
		const size_t size = sa.size();
		bwt.resize(size);
		for (size_t i = 0; i < size; i++) {
			if (sa[i] > 0) {
				bwt[i] = s[sa[i] - 1];
			} else {
				bwt[i] = s[size - 1];
			}
		}
	}
	size_t getBitLen(size_t x) const
	{
		if (x == 0) return 1;
		size_t ret = 0;
		while (x > 0) {
			x >>= 1;
			ret++;
		}
		return ret;
	}
public:
	FMindexT()
		: skip_(8)
		, charNum_(0)
	{
	}

	/*
		[begin, end)
		replace '\0' in [begin, end) with space
		append '\0' at the end of [begin, end)
	*/
	template<class Iter>
	void init(Iter begin, Iter end, int skip = 8)
	{
		if (skip <= 0) {
			throw cybozu::Exception("FMindexT:buildFMindex:skip is positive") << skip;
		}
		skip_ = skip;
		Vec v;
		initCf(v, begin, end);
		const size_t dataSize = v.size();

		Vec32 sa;
		sa.resize(dataSize);
		if (saisxx(&v[0], &sa[0], (int)dataSize, (int)charNum_) == -1) {
			throw cybozu::Exception("FMindexT:init:saisxx");
		}
		Vec bwt;
		initBwt(bwt, v, sa);
		wm.init(bwt, getBitLen(charNum_));

		alignedPos.resize(dataSize);
		for (size_t i = 0; i < dataSize; i++) {
{'fraction_non_alphanumeric': 0.16473544604216112, 'fraction_numerical': 0.024849923216529388, 'mean_word_length': 3.554354736172918, 'pattern_counts': {'":': 0, '<': 79, '<?xml version=': 0, '>': 49, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2329769', 'n_tokens_mistral': 3365, 'n_tokens_neox': 2956, 'n_words': 752}