置换索引(KWIC index)的简单例子
博客专区 > D-dragon 的博客 > 博客详情
置换索引(KWIC index)的简单例子
D-dragon 发表于11个月前
置换索引(KWIC index)的简单例子
  • 发表于 11个月前
  • 阅读 47
  • 收藏 0
  • 点赞 0
  • 评论 0

【腾讯云】如何购买服务器最划算?>>>   

置换索引(permuted index)又叫KWIC(keyword-in-context)索引,其实个人觉得这个“置换”用得不太准确,因为permute意思是“序列改变”,但这个中文翻译过来也很难找到相对应的词,翻译成“序列改变索引”说不定还好些。

最近在看《accelerated c++》这个书时,在第五章发现一个习题,如下:

设计和实现一个程序来产生一直置换索引。在一个置换索引中,每一个短语都是这个短语的每一个单词作为索引的。因此,假如有如下的输入:

The quick brown fox 
jumped over the fence

则输出:

      The quick     brown fox 
jumped over the     fence
The quick brown     fox 
                    jumped over the fence
         jumped     over the fence
            The     quick brown fox 
    jumped over     the fence
                    The quick brown fox

 

这个题的意思读了很久没读懂,后来看代码才明白。意思是每个单词都会生成一个索引,虽然索引只是一句话中的一个单词,但是还是要将这一句话完整的呈现出来(用空格或者tab键隔开),最后通过字母排序显示。比如The quick brown fox中,会产生四个索引,但是brown按字母排序会排在第一,而在brown后面的就只有fox,所以The quick与brown fox就分开显示。

但是这个算法却非常有难度,书的提示如下:

1,读入输入的每一行并对每一行输入产生一个轮转的集合。每一个轮转都把输入的下一个单词放在第一个位置上,并把原先的第一个单词旋转到短语的末尾。因此输入的第一行所表示的短语的输出将会是:

  1. The quick brown fox
    quick brown fox The
    brown fox The quick
    fox The quick brown

当然,重要的是要知道最初的短语是在哪里结束,而轮转的开头又是从哪里开始的。

2,对这些轮转集合排序。

3,反向轮转并输出置换索引,其中包含了查找分隔符号、把短语重新连接到一起以及以正确的格式输出短语等操作。

本人以前是做JAVA开发的,对C++很不熟悉,只能在网上找答案,中文的资料几乎没什么用,只能找英文的来学习。

1,首先解决第一个问题,先定义一个结构struct:

struct Rotation {
  vector<string>::size_type first;
  vector<string> words; //保存单行输入
};

first字段的意思等会再说,因为没看到有关的代码,就不能很好理解为什么要这个字段。下面写轮转的算法:

vector<Rotation> rotate_line(const string& line) {
  vector<Rotation> rotations;
  vector<string> words = split(line);
	
  //每次循环都将vector中的第一个字符串旋转到最后去 
  for (vector<string>::size_type i = 0; i < words.size(); ++i) {
    Rotation rot = {words.size() - i, words};
    rotations.push_back(rot);
    rotate(words.begin(), words.begin() + 1, words.end()); 
  }
  return rotations;
}

这个函数的引用了<algorithm>中的rotate函数,使用了每次将一行字符串的第一个单词放在该行的末尾,而且还记录了轮转单词的位置。比如输入The quick brown fox,那么这个函数返回vector中,数据如下:

first:4, words :The quick brown fox
first:3, words :quick brown fox The
first:2, words :brown fox The quick
first:1, words :fox The quick brown

这个first目前的意思,大概可以理解为索引单词前面的单词数目。因为原句为The quick brown fox,所以brown fox The quick,就是向前移动了两步,因此first为2。

当然,上面的代码只实现了单行文本的轮转,输入多行又怎么办呢?

vector<Rotation> rotate_lines(const vector<string>& lines) {
  vector<Rotation> rotations;
  for (vector<string>::size_type i = 0; i < lines.size(); ++i) {
    vector<Rotation> new_rotations = rotate_line(lines[i]);
    rotations.insert(rotations.end(), new_rotations.begin(), new_rotations.end());
  }
  return rotations;
}

输入题中的两行文本,则数据如下:

first=4,words :The quick brown fox
first=3,words :quick brown fox The
first=2,words :brown fox The quick
first=1,words :fox The quick brown
first=4,words :jumped over the fence
first=3,words :over the fence jumped
first=2,words :the fence jumped over
first=1,words :fence jumped over the

也就是把所有生成的索引,都放在一个vector里面,因为这样,才方便后面的排序。

2,下面来实现排序功能:

string toLowerCase(const string& data){
	string str=data;//注意,这里的str与data必须要有同样大小的容量,所以这里干脆直接初始化为data的复本
	std::transform(data.begin(), data.end(), str.begin(), ::tolower);
	return str;
}

vector<string> lowcase(const vector<string>& data){
	vector<string> vect;
	for(vector<string>::const_iterator it = data.begin();it != data.end(); ++it){
		vect.push_back(toLowerCase(*it));
	}
	return vect;
}

bool compare(const Rotation& x, const Rotation& y) {
  return lowcase(x.words)< lowcase(y.words);
}

...

sort(rotations.begin(), rotations.end(), compare);

string没有直接转换为小写的函数,所以必须手动实现一个,为什么要实现都用小写字母的比较呢?因为默认是按ascii字符的方式排序的,所以The > the,如果不转换,那么题中的The quick brown fox这个索引,肯定是排在第一,因为只是The这个单词的首字母是大写字母,它的 ascii值肯定最小。

3,输出。有一点要注意,那就是索引单词的前面要用空格来分隔,代码如下:

void print_rotations(vector<Rotation> rotations) {
  vector<string> first_halves;
  vector<string> second_halves;
  string::size_type max_first_half_width = 0;

  for (vector<Rotation>::size_type i = 0; i < rotations.size(); ++i) {
    Rotation rot = rotations[i];
    string first_half, second_half;

    for (vector<string>::size_type j = rot.first; j < rot.words.size(); ++j)
      first_half += rot.words[j] + " ";

    first_halves.push_back(first_half);

    if (first_half.size() > max_first_half_width)
      max_first_half_width = first_half.size();

    for (vector<string>::size_type j = 0; j < rot.first; ++j)
      second_half += rot.words[j] + " ";

    second_halves.push_back(second_half);
  }

  for (vector<string>::size_type i = 0; i < first_halves.size(); ++i) {
    cout << setw(max_first_half_width);
    cout << first_halves[i];
    cout << "\t";
    cout << second_halves[i];
    cout << endl;
  }
}

这段代码可以分两部分来看,其中first_halves表示间隔的前面部分,而second_halves表示部分,如:

The quick     brown fox 

则first_halves代表the quick,而second_halves代码brown fox部分。而max_first_half_width则代表单行的最大宽度,目的是让间隔的两边对齐(用空格补齐)。

 

完全代码如下:

split.h代码:

#ifndef GUARD_split_h
#define GUARD_split_h

#include <vector>
#include <string>
std::vector<std::string> split(const std::string&);

#endif

split.cpp代码如下:

#include <cctype>
#include <string>
#include <vector>

#include "split.h"

using std::vector;
using std::string;

#ifndef _MSC_VER
using std::isspace;
#endif

vector<string> split(const string& s) {
  vector<string> ret;
  typedef string::size_type string_size;
  string_size i = 0;

  // invariant: we have processed characters `['original value of `i', `i)'
  while (i != s.size()) {
    // ignore leading blanks
    // invariant: characters in range `['original `i', current `i)' are all spaces
    while (i != s.size() && isspace(s[i]))
      ++i;

    // find end of next word
    string_size j = i;
    // invariant: none of the characters in range `['original `j', current `j)' is a space
    while (j != s.size() && !isspace(s[j]))
      ++j;

    // if we found some nonwhitespace characters
    if (i != j) {
      // copy from `s' starting at `i' and taking `j' `\-' `i' chars
      ret.push_back(s.substr(i, j - i));
      i = j;
    }
  }

  return ret;
}

5-1.cpp如下:

#include <algorithm> //rotate algorithm
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

#include "split.h"

using namespace std;

struct Rotation {
  vector<string>::size_type first;
  vector<string> words;
};

vector<string> read_lines() {
  vector<string> lines;
  string line;

  while (getline(cin, line))
    lines.push_back(line);

  return lines;
}

vector<Rotation> rotate_line(const string& line) {
  vector<Rotation> rotations;
  vector<string> words = split(line);
	
  //每次循环都将vector中的第一个字符串旋转到最后去 
  for (vector<string>::size_type i = 0; i < words.size(); ++i) {
    Rotation rot = {words.size() - i, words};
    rotations.push_back(rot);
    rotate(words.begin(), words.begin() + 1, words.end()); 
  }
  
  return rotations;
}


vector<Rotation> rotate_lines(const vector<string>& lines) {
  vector<Rotation> rotations;

  for (vector<string>::size_type i = 0; i < lines.size(); ++i) {
    vector<Rotation> new_rotations = rotate_line(lines[i]);
    rotations.insert(rotations.end(), new_rotations.begin(), new_rotations.end());
  }

  return rotations;
}

string toLowerCase(const string& data){
	string str=data;
	std::transform(data.begin(), data.end(), str.begin(), ::tolower);
	return str;
}

vector<string> lowcase(const vector<string>& data){
	vector<string> vect;
	for(vector<string>::const_iterator it = data.begin();it != data.end(); ++it){
		vect.push_back(toLowerCase(*it));
	}
	return vect;
}

bool compare(const Rotation& x, const Rotation& y) {
  return lowcase(x.words)< lowcase(y.words);
}

void print_rotations(vector<Rotation> rotations) {
  vector<string> first_halves;
  vector<string> second_halves;
  string::size_type max_first_half_width = 0;

  for (vector<Rotation>::size_type i = 0; i < rotations.size(); ++i) {
    Rotation rot = rotations[i];
    string first_half, second_half;

    for (vector<string>::size_type j = rot.first; j < rot.words.size(); ++j)
      first_half += rot.words[j] + " ";

    first_halves.push_back(first_half);

    if (first_half.size() > max_first_half_width)
      max_first_half_width = first_half.size();

    for (vector<string>::size_type j = 0; j < rot.first; ++j)
      second_half += rot.words[j] + " ";

    second_halves.push_back(second_half);
  }

  for (vector<string>::size_type i = 0; i < first_halves.size(); ++i) {
    cout << setw(max_first_half_width);
    cout << first_halves[i];
    cout << "\t";
    cout << second_halves[i];
    cout << endl;
  }
}

int main() {
  vector<string> lines = read_lines();
  vector<Rotation> rotations = rotate_lines(lines);
  sort(rotations.begin(), rotations.end(), compare);
  print_rotations(rotations);

  return 0;
}

至此,结束。

标签: KWIC
共有 人打赏支持
粉丝 6
博文 37
码字总数 35447
×
D-dragon
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: