Untitled
unknown
c_cpp
a year ago
9.4 kB
5
Indexable
#define FILE_EXTENSION ".txt"
#include<fstream>
#include<string>
#include<cstring>
#include<vector>
#include<iostream>
#include<unordered_map>
#include<algorithm>
#include<set>
#include <filesystem>
#include <unordered_set>
#include <chrono>
using namespace std;
namespace fs = std::filesystem;
class TrieNode {
public:
TrieNode* child[26];
TrieNode* parent[26];
// bitset<5000005> prefix(0);
// bitset<5000005> suffix(0);
bool terminate, terminate_parent;
TrieNode() {
for (int i = 0; i < 26; i++) {
child[i] = nullptr;
parent[i] = nullptr;
}
terminate_parent = false;
terminate = false;
}
};
class Trie {
public:
TrieNode* root;
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* p = root;
TrieNode* back = root;
int len = word.size();
for (auto &c : word) {
int index = 0;
if (c >= 'A' && c <= 'Z')
index = c - 'A';
else if (c >= 'a' && c <= 'z')
index = c - 'a';
if (p->child[index] == nullptr)
p->child[index] = new TrieNode();
p = p->child[index];
}
for(int i = len-1; i >= 0; i--) {
int index = 0;
if (word[i] >= 'A' && word[i] <= 'Z')
index = word[i] - 'A';
else if (word[i] >= 'a' && word[i] <= 'z')
index = word[i] - 'a';
if (back->parent[index] == nullptr)
back->parent[index] = new TrieNode();
back = back->parent[index];
}
p->terminate = true;
back->terminate_parent = true;
}
bool WildCardSearch(string word, int index, TrieNode* cur) {
int len = word.size();
cout << index << " ";
// cout << word[index] << endl;
if (index == len-2) {
return cur->terminate;
}
if (word[index] == '*') {
while (index+1 < len && word[index+1] == '*') {
index++; // avoid multiple '*'
}
if (index == len-2) {
return true;
}
bool result = false;
for (int i = 0; i < 26; i++) {
if (cur->child[i] != nullptr) {
// cout << word[index+1] << " " << i << endl;
// if (index+1 < len && (i == (word[index+1] - 'a') || i == (word[index+1] - 'A')) && WildCardSearch(word, index + 1, cur->child[i])) {
// result = true;
// }
if (WildCardSearch(word, index + 1, cur->child[i])) {
result = true;
}
if (WildCardSearch(word, index, cur->child[i])) {
result = true;
}
}
}
return result;
}
else {
int charIndex = 0;
if (word[index] >= 'A' && word[index] <= 'Z') {
charIndex = word[index] - 'A';
}
else if (word[index] >= 'a' && word[index] <= 'z') {
charIndex = word[index] - 'a';
}
if (cur->child[charIndex] == nullptr) {
return false;
}
return WildCardSearch(word, index + 1, cur->child[charIndex]);
}
}
bool SuffixSearch(string word) {
TrieNode* p = root;
int len = word.size();
for(int i = len-1; i >= 0; i--) {
if(isalpha(word[i])) {
int index = 0;
if(word[i] >= 'A' && word[i] <= 'Z')
index = word[i]-'A';
else if(word[i] >= 'a' && word[i] <= 'z')
index = word[i]-'a';
if(p->parent[index] == nullptr)
return false;
p = p->parent[index];
}
}
return true;
}
bool search(string word, bool prefix = false) {
TrieNode* p = root;
for(auto c: word) {
if(isalpha(c)) {
int index = 0;
if(c >= 'A' && c <= 'Z')
index = c-'A';
else if(c >= 'a' && c <= 'z')
index = c-'a';
if(p->child[index] == nullptr)
return false;
p = p->child[index];
}
}
if(prefix == false) return p->terminate;
return true;
}
bool startsWith(string prefix) {
return search(prefix, true);
}
};
// Utility Func
// string parser : output vector of strings (words) after parsing
vector<string> word_parse(vector<string> tmp_string){
vector<string> parse_string;
for(auto& word : tmp_string){
string new_str;
for(auto &ch : word){
if(isalpha(ch))
new_str += ch;
}
parse_string.emplace_back(new_str);
}
return parse_string;
}
vector<string> split(const string& str, const string& delim) {
vector<string> res;
if("" == str) return res;
char * strs = new char[str.length() + 1] ;
strcpy(strs, str.c_str());
char * d = new char[delim.length() + 1];
strcpy(d, delim.c_str());
char *p = strtok(strs, d);
while(p) {
string s = p;
res.push_back(s);
p = strtok(nullptr, d);
}
return res;
}
int checkType(string s) {
if(s[0] == '"') {
return 0; // exact word
}
else if(s[0] == '*' && s[s.size()-1] == '*') {
return 2; // suffix word
}
else if(s[0] == '<' && s[s.size()-1] == '>') {
return 3; // wildcard search
}
else if(s == "/" || s == "-" || s == "+") // operator
return 4;
else {
return 1; // prefix
}
}
int main(int argc, char *argv[]) {
// INPUT :
// 1. data directory in data folder
// 2. number of txt files
// 3. output route
auto start_time = std::chrono::high_resolution_clock::now();
string data_dir = argv[1] + string("/");
string query = string(argv[2]);
ifstream fi(query, ios::in);
string output = string(argv[3]);
string file, title_name, tmp, q_tmp;
ofstream outputFile(output);
vector<string> tmp_string;
int cnt = 0; // count of data
const int EXACT = 0;
const int PREFIX = 1;
const int SUFFIX = 2;
const int WILDCARD = 3;
// GET TITLENAME WORD ARRAY
vector<string> title;
unordered_map<string, Trie*> mp;
/*
create trie of every data
*/
vector<string> file_paths;
int i = 0;
while (1) {
std::string current_file_path = data_dir + std::to_string(i) + ".txt";
if (fs::exists(current_file_path)) {
file_paths.emplace_back(current_file_path);
// cout << current_file_path << endl;
}
else {
break;
}
i++;
}
for (auto file_path : file_paths) {
ifstream inputFile(file_path);
getline(inputFile, title_name);
title.emplace_back(title_name);
cnt++;
string tmp;
while (getline(inputFile, tmp)) {
// GET CONTENT WORD VECTOR
vector<string> tmp_string = split(tmp, " ");
// PARSE CONTENT
vector<string> content = word_parse(tmp_string);
for (auto word : content) {
if (mp[title_name] == nullptr) {
mp[title_name] = new Trie();
}
mp[title_name]->insert(word);
}
}
inputFile.close();
}
set<int> ans_title;
unordered_set<int> title_tmp;
int n = 1;
while(getline(fi, q_tmp)) { // get seperate query
int merge_type = -1;
vector<string> q = split(q_tmp, " ");
outputFile << n++ <<"\n";
for(auto it_query : q) { // iterate all the query
string front = "", end = "";
int type = checkType(it_query);
if(type == 4) {
if(it_query == "/") {
merge_type = 0;
}
else if(it_query == "-") {
merge_type = 1;
}
else if(it_query == "+") {
merge_type = 2;
}
continue;
}
for(int i = 0; i < cnt; i++) {
auto data = mp[title[i]];
if(type == EXACT) {
if(data->search(it_query))
title_tmp.insert(i);
}
else if(type == PREFIX) {
if(data->startsWith(it_query))
title_tmp.insert(i);
}
else if(type == SUFFIX) {
if(data->SuffixSearch(it_query))
title_tmp.insert(i);
}
else if(type == WILDCARD) {
if(data->WildCardSearch(it_query, 1, data->root))
title_tmp.insert(i);
}
}
if(merge_type == 0) { // OR
for(auto it : title_tmp) {
ans_title.insert(it);
}
}
else if(merge_type == 1) { // NOT
for (auto it = ans_title.begin(); it != ans_title.end();) {
if (title_tmp.count(*it) == 1)
it = ans_title.erase(it);
else
++it;
}
}
else if(merge_type == 2) { // AND
for (auto it = ans_title.begin(); it != ans_title.end();) {
if (title_tmp.count(*it) == 0)
it = ans_title.erase(it);
else
++it;
}
}
else { // -1, don't need to merge
for(auto it: title_tmp) {
ans_title.insert(it);
}
}
title_tmp.clear();
merge_type = -1;
}
if(ans_title.empty()) {
outputFile << "Not Found!\n";
}
else {
for(auto it : ans_title) {
outputFile << title[it] << "\n";
}
}
ans_title.clear();
}
fi.close();
outputFile.close();
auto end_time = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end_time - start_time);
std::cout << "程式執行時間: " << duration.count()/1000 << " ms" << std::endl;
}
// 1. UPPERCASE CHARACTER & LOWERCASE CHARACTER ARE SEEN AS SAME.
// 2. FOR SPECIAL CHARACTER OR DIGITS IN CONTENT OR TITLE -> PLEASE JUST IGNORE, YOU WONT NEED TO CONSIDER IT.
// EG : "AB?AB" WILL BE SEEN AS "ABAB", "I AM SO SURPRISE!" WILL BE SEEN AS WORD ARRAY AS ["I", "AM", "SO", "SURPRISE"].
// 3. THE OPERATOR IN "QUERY.TXT" IS LEFT ASSOCIATIVE
// EG : A + B / C == (A + B) / C
//
//////////////////////////////////////////////////////////
Editor is loading...
Leave a Comment