7

我正在寻找一种算法，该算法将采用字符串向量v1并返回一个相似的字符串向量，v2其中每个字符串的长度小于x字符长度并且是唯一的。中的字符串v1可能不是唯一的。

虽然我需要在 中接受 ASCII，但在需要插入新字符时v1，我宁愿只插入字母数字字符 ( [A-Za-z0-9])。

显然这里有三个警告：

  1. 对于 and 的某些值，v1不可能x是唯一的v2。例如，当v1有 37 个元素和x == 1.

  2. 问题中指定的“类似”是主观的。字符串将面向用户，并且可能是简短的自然语言短语（例如“颜色数量”）。我希望人类能够尽可能轻松地将原始字符串映射到缩短的字符串。这可能意味着利用启发式方法，例如disemvoweling。因为我的相似性构造可能没有客观的衡量标准（字符串距离在这里可能不是最有用的，尽管它可能）我对什么是好的判断将是任意的。该方法应该适用于英语 - 其他语言无关紧要。

显然这是一个（编程）与语言无关的问题，但我会看好 python 中的实现（因为我发现它的字符串处理语言直截了当）。

4

3 回答 3

1

素描 -

开发一个减少英文字符串大小的函数列表。将功能从最隐蔽到最隐蔽排序。

对于中的每个字符串，v1重复应用一个模糊函数，直到它不能再减小字符串的大小，然后继续执行下一个函数。

当达到所需的大小时x，验证缩减的字符串相对于v2. 如果是，添加到v2，如果不是，继续应用遮蔽功能。

以下是一些主观上从最小到最模糊排序的减小函数大小的想法。（随机选择旨在增加减少的字符串唯一的概率。）

  1. 用一个空格替换随机出现的两个空格字符
  2. 用单个空格替换随机出现的标点符号后跟空格
  3. 随机删除一个同时也是杀戮列表成员的单个字符单词（例如“I”、“a”）
  4. 随机删除一个两个字符的单词，它也是杀死列表的成员（例如“an”、“of”）
  5. 随机删除一个三个字符的单词，它也是杀死列表的成员（例如“the”、“and”）
  6. 用前三个和最后一个字符组成的单词替换五个或更多字符的单词（例如“number”变成“numr”，“colours”变成“colrs”）
  7. 随机删除一个元音
  8. 删除 v1 中大量字符串中出现的单词。这个想法是非常常见的单词价值很低。
  9. 根据字典（同义词库）（例如http://www.baac.net/michael/plates/index.html）将单词/短语翻译成更短的“vanity license plate”单词

（注意：最后两个函数需要访问初始未更改的字符串，以及未更改的单词和已更改的单词之间的对应关系。）

于 2012-04-02T16:08:16.843 回答
1

关于在 python 中执行此操作的一些注释/指示。

  1. 使用bisect 模块来保存您的结果数组，以便轻松发现潜在的非唯一性。即使v1已经排序，这也是有帮助的（例如name，enemy在去元音之后会发生碰撞）
  2. Disemvoweling 可以通过简单地调用.translate(None, "aeiouyAEIOUY")字符串来实现。
  3. 如果出现重复，您可以尝试首先通过小写所有结果并使用 swapcase 作为“位掩码”来解决冲突，即 aaa 的多次出现["aaa", "aaA", "aAa", "aAA"]等，如果这还不够，则从末尾开始“递增”字符，直到一个非- 找到碰撞标识符，例如。["aa"]*7会成为 ["aa", "aA", "Aa", "AA", "ab", "aB", "Ab"]
于 2012-04-02T07:55:41.477 回答
-1 
def split_len(seq, length):
    return [seq[i:i+length] for i in range(0, len(seq), length)]
newListOfString=[]
for item in listOfStrings:
    newListOfString.append(split_len(item,8)[0])

这将返回第一个八个字符。

于 2012-04-02T06:52:21.753 回答