文档章节

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

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

至此,结束。

© 著作权归作者所有

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

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

z_jordon ⋅ 2015/05/01 ⋅ 0

扬尼斯定律:程序员的开发效率每6年提高一倍

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

oschina ⋅ 2012/07/04 ⋅ 18

OpenType™ Layout通用表格式

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

WolfCS ⋅ 2013/06/29 ⋅ 0

数据库优化之索引

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

trayvon ⋅ 2015/12/08 ⋅ 0

pgsql全文索引

pgsql 全文索引 先给个实际的效果,在hotel数据库,进入poi_detail数据表,执行指令 select name from poidetail where totsvector('senaeanword'::regconfig,lower(name)) @@ plaintotsquer......

颓废的幻想者 ⋅ 2013/10/12 ⋅ 2

Elasticsearch上手——几个基本概念

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

kjmeng ⋅ 2017/01/26 ⋅ 0

Python3学习笔记——列表(一)

在Python中,列表是由一系列的按特定顺序排列的元素组成的数据类型。列表的元素可以是任意类型,一个列表中的元素类型可以不相同。简单的来说,列表就相当于加强版数组(C语言中),它和Jav...

equalsYU ⋅ 05/24 ⋅ 0

java实现插入、冒泡、选择、快速排序、二分查找

一. 直接插入排序 void insertSort(int[] a){ for(int i=1;i<a.length; i++){ if (a[i]<a[i-1]){ temp = a[i]; //1 a[i] = a[i-1]; //2 // 继续和前面的进行比较 for(int j=i-2; j>=0; j--){......

xinyitianii ⋅ 2014/06/09 ⋅ 0

lucene学习笔记一之初识lucene

承接第一篇的博文所述,建一个lucene的小例子: 开发环境:本人用的IDE是myeclipse10,jdk1.7(开发环境不是硬性要求,只要能运行程序就行) 1.首先我们新建java项目luce_01,在项目目录上点击新建文...

程开华 ⋅ 2014/01/08 ⋅ 0

Java for Web学习笔记(一一九):搜索(1)JPA的动态条件搜索(上)

关于搜索 数据库中的index 需要平衡考虑: 索引会使查询更快 索引会使持续化更慢 这需要我们具体个例具体衡量。 一般来讲95%的请求都应还有index,多个条件的请求,必须有一个带有index。 LI...

flowingflying ⋅ 04/14 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Spring | IOC AOP 注解 简单使用

写在前面的话 很久没更新笔记了,有人会抱怨:小冯啊,你是不是在偷懒啊,没有学习了。老哥,真的冤枉:我觉得我自己很菜,还在努力学习呢,正在学习Vue.js做管理系统呢。即便这样,我还是不...

Wenyi_Feng ⋅ 今天 ⋅ 0

博客迁移到 https://www.jianshu.com/u/aa501451a235

博客迁移到 https://www.jianshu.com/u/aa501451a235 本博客不再更新

为为02 ⋅ 今天 ⋅ 0

win10怎么彻底关闭自动更新

win10自带的更新每天都很多,每一次下载都要占用大量网络,而且安装要等得时间也蛮久的。 工具/原料 Win10 方法/步骤 单击左下角开始菜单点击设置图标进入设置界面 在设置窗口中输入“服务”...

阿K1225 ⋅ 今天 ⋅ 0

Elasticsearch 6.3.0 SQL功能使用案例分享

The best elasticsearch highlevel java rest api-----bboss Elasticsearch 6.3.0 官方新推出的SQL检索插件非常不错,本文一个实际案例来介绍其使用方法。 1.代码中的sql检索 @Testpu...

bboss ⋅ 今天 ⋅ 0

informix数据库在linux中的安装以及用java/c/c++访问

一、安装前准备 安装JDK(略) 到IBM官网上下载informix软件:iif.12.10.FC9DE.linux-x86_64.tar放在某个大家都可以访问的目录比如:/mypkg,并解压到该目录下。 我也放到了百度云和天翼云上...

wangxuwei ⋅ 今天 ⋅ 0

PHP语言系统ZBLOG或许无法重现月光博客的闪耀历史[图]

最近在写博客,希望通过自己努力打造一个优秀的教育类主题博客,名动江湖,但是问题来了,现在写博客还有前途吗?面对强大的自媒体站点围剿,还有信心和可能型吗? 至于程序部分,我选择了P...

原创小博客 ⋅ 今天 ⋅ 0

IntelliJ IDEA 2018.1新特性

工欲善其事必先利其器,如果有一款IDE可以让你更高效地专注于开发以及源码阅读,为什么不试一试? 本文转载自:netty技术内幕 3月27日,jetbrains正式发布期待已久的IntelliJ IDEA 2018.1,再...

Romane ⋅ 今天 ⋅ 0

浅谈设计模式之工厂模式

工厂模式(Factory Pattern)是 Java 中最常用的设计模式之一。这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式。 在工厂模式中,我们在创建对象时不会对客户端暴露创建逻...

佛系程序猿灬 ⋅ 今天 ⋅ 0

Dockerfile基础命令总结

FROM 指定使用的基础base image FROM scratch # 制作base image ,不使用任何基础imageFROM centos # 使用base imageFROM ubuntu:14.04 尽量使用官方的base image,为了安全 LABEL 描述作...

ExtreU ⋅ 昨天 ⋅ 0

存储,对比私有云和公有云的不同

导读 说起公共存储,很难不与后网络公司时代的选择性外包联系起来,但尽管如此,它还是具备着简单和固有的可用性。公共存储的名字听起来也缺乏专有性,很像是把东西直接堆放在那里而不会得到...

问题终结者 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部