文档章节

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

D
 D-dragon
发布于 2017/02/26 21:49
字数 1908
阅读 155
收藏 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
博文 40
码字总数 40536
作品 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
数据库优化之索引

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

trayvon
2015/12/08
160
0
Elasticsearch上手——几个基本概念

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

kjmeng
2017/01/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

visualVm 中的 visual GC说明

visual GC 不是 visualVM 自带的,需要安装插件。 步聚:菜单栏 (Tools) - > plugins - > Avaiable Plugins 中就选择安装 Spaces: 各个分代的内存使用情况。 特别说明:风格有分灰色部分,...

Canaan_
昨天
1
0
学习设计模式——生成器模式

1. 认识生成器模式 1. 定义:将一个复杂对象的构建与它的表示分离,使得同样的构建过程可以创建不同的表示 2. 组成: Builder:生成器接口,定义创建一个Product对象所需要的各个组件的操作,...

江左煤郎
昨天
0
0
C语言精要(第二章:基本数据类型)

2.1 C语言基本数据类型 在计算机术语中,把⼆进制数中的某⼀位数又称为⼀个⽐特(bit)。⽐特这个单位对于计算机⽽⾔,在度量上是最⼩的单位。除了⽐特之外,还有字节(byte)这个术语。⼀个...

ryanliue
昨天
0
0
实现下拉菜单多选框效果

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><html><li>工作意愿地:<%-- <c:forEach items="${list}" var="list"><input type="checkbox" value="${list......

lanjian28
昨天
1
0
scala的视图界定

在上一篇帧子的代码中,如果main函数中不是用字符串而是用数字则程序不能正常编译: class Pair[T <: Comparable[T]](val first:T,val second:T) //类型T必须要是Comparable接口的子类(即...

whoisliang
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部