文档章节

置换索引(KWIC index)的简单例子

D
 D-dragon
发布于 2017/02/26 21:49
字数 1908
阅读 208
收藏 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;
}

至此,结束。

© 著作权归作者所有

共有 人打赏支持
D
粉丝 6
博文 41
码字总数 40861
作品 0
资阳
程序员
私信 提问
基于管道过滤器实现的kwic实现

KWIC索引系统接受一些行,每行有若干字,每个字由若干字符组成;每行都可以循环移位。重复地把第一个字删除,然后接到行末; KWIC把所有行的各种移位情况按照字母表顺序输出。 在网上找了一个...

z_jordon
2015/05/01
0
0
OpenType™ Layout通用表格式

OpenType Layout由5个表组成:Glyph置换表(GSUB),Glyph定位表(GPOS),基线表(BASE), Justification表 (JSTF),和Glyph定义表(GDEF)。这些表使用了一些相同的数据格式。 本章将解释一下在所...

WolfCS
2013/06/29
0
0
扬尼斯定律:程序员的开发效率每6年提高一倍

我不断的听到各种关于“软件危机”的警言,以及关于软件开发缺少过程规范的批评。我做编程工作超过15年,我认为这些言论基本上都是错的:我确信我能在很短的时间里用如今的开发工具复制出15年...

oschina
2012/07/04
2.7K
18
Elasticsearch上手——几个基本概念

Elasticsearch的说明文档中,基本概念(Basic Concepts)一节中提到了一些术语,结合实践经验,尝试重新理解一下。 Document(文档) 文档是Elasticsearch存储和建立索引的基本单位,比如一篇...

kjmeng
2017/01/26
0
0
数据库优化之索引

一 、引言 首先我们来思考一下什么是索引?索引的作用是什么?操作系统的文件索引和数据库的索引有什么不同? 什么是索引?对于这个问题我们可以打一个比喻,索引相对于文件的作用,就好比是...

trayvon
2015/12/08
160
0

没有更多内容

加载失败,请刷新页面

加载更多

PHP生成CSV之内部换行

当我们使用PHP将采集到的文件内容保存到csv文件时,往往需要将采集内容进行二次过滤处理才能得到需要的内容。比如网页中的换行符,空格符等等。 对于空格等处理起来都比较简单,这里我们单独...

豆花饭烧土豆
今天
2
0
使用 mjml 生成 thymeleaf 邮件框架模板

发邮件算是系统开发的一个基本需求了,不过搞邮件模板实在是件恶心事,估计搞过的同仁都有体会。 得支持多种客户端 支持响应式 疼彻心扉的 outlook 多数客户端只支持 inline 形式的 css 布局...

郁也风
今天
8
0
让哲学照亮我们的人生——读《医务工作者需要学点哲学》有感2600字

让哲学照亮我们的人生——读《医务工作者需要学点哲学》有感2600字: 作者:孙冬梅;以前读韩国前总统朴槿惠的著作《绝望锻炼了我》时,里面有一句话令我印象深刻,她说“在我最困难的时期,...

原创小博客
今天
4
0
JAVA-四元数类

public class Quaternion { private final double x0, x1, x2, x3; // 四元数构造函数 public Quaternion(double x0, double x1, double x2, double x3) { this.x0 = ......

Pulsar-V
今天
18
0
Xshell利用Xftp传输文件,使用pure-ftpd搭建ftp服务

Xftp传输文件 如果已经通过Xshell登录到服务器,此时可以使用快捷键ctrl+alt+f 打开Xftp并展示Xshell当前的目录,之后直接拖拽传输文件即可。 pure-ftpd搭建ftp服务 pure-ftpd要比vsftp简单,...

野雪球
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部