代码之家 › 专栏 › 技术社区 › thomasrutter

获取字符串的数字/规范化表示,以帮助数据库中标题的“自然排序顺序”

natural-sort string algorithm mysql

thomasrutter · 技术社区 · 15 年前

我想在表中存储一个额外的列作为“排序值”,它是标题列的数字表示,这样,这些值的顺序表示字符串的自然字母排序顺序。也就是说,这样我就可以检索按排序值排序的行,它们将以自然的排序顺序排列——当我插入新行时,我可以生成数值,并知道相对于其他行的值将代表字符串在字母搜索中的位置,精确到前x个字母左右。

原因有两个:首先,我想要一个比数据库服务器提供的简单的排序更自然的排序,比如“the”和“a”以及标点符号在开始时被忽略,数字被“自然”处理。

第二,这是针对具有大量排列的索引——它将节省空间,并且可能在遍历具有多行的索引时节省时间。

我所追求的是将字符串转换为该数值的算法,或者只是,我想,一个标准化的字符串值。

我使用的是php和mysql。

恐怕“使用natcasesort()从数据库中提取所有内容并在php中排序”并不是这种特殊情况的解决方案,因为我希望在行到达join或limit子句之前按排序顺序检索行(使用order by和group by)。谢谢。

编辑:

谢谢你的回答。我刚刚想到我的应用程序使用UTF-8这一事实是非常相关的。有了这一点,我认为用压缩/数字形式表示字符串初始部分的实用性是一种延伸,可能只是某种规范化形式(所有内容都是折叠的,数字是零填充的,并且尽可能多的字符被规范化为其根ie_到a)是合适的。

2 回复 | 直到 15 年前

j_random_hacker 15 年前

部分 “精确到前X个字母左右” 至关重要,因为完全准确的数字分配是不可能的。为了看到这一点,假设你的 title 列为 varchar(50) 你想用32位 integer sort_order 列。然后你可以存储(255^51-1)不同的标题,每个标题都需要不同的 分类顺序 值--但只有2^32个不同 分类顺序 价值观。即使你说你永远不会添加超过2^32行,你也需要提前知道他们将拥有哪些标题,以便想出一个避免重新分配所有标题的方案。 分类顺序 每次插入行时的值。

虽然“理论上完美”的解决方案是不可能的,但仍然有可能得到一个实际的“近似”系统,该系统应能以完美的精度工作多达数百万行。最简单的方法是使用浮点类型。首先,按排序顺序列出行并分配第一行A 分类顺序 值为1.0,第二个值为2.0,依此类推。然后,每当插入一行时,设置它的 分类顺序 以排序顺序到达两边行的中点(即平均值)。如果新添加的行在所有现有行之前(或之后),只需将其设置为小于(或大于)上一个最小值(或最大值)的1。 分类顺序 价值。

最好从零开始重新分配数字(如在初始构建步骤中)以定期或在大量更新之后“平滑”这些值。特别是如果桌子开始小,然后变大,你可能会发现一些数字的“聚”在最后。

thomasrutter 15 年前

谢谢你的回答。我只是想用我要用的解决方案更新人们。我采取了一种不同于我在问题中设想的方法。

概括地说,我想存储一个字符串的表示,这样当以二进制顺序检索时,我为“8英里”存储的任何内容都将在为“101个数据”存储的任何内容之前排序。

对于字符串中的每个数字(基本上是一个数字序列),我在它们前面插入一个数字,描述数字的位数。

所以,“8”变成“18”,“101”变成“3101”。它为数字增加了一些冗余,因为您使用的数字超过了需要的数量,并且某些值将不存在,但它们现在具有二进制排序将数字按数字顺序排序的属性。”101“会在8”之前排序,这是不需要的。在加上这个额外的数字后,“18”在“3101”之前排序。

注意:如果数字长9位或更多,我会在开头加上两位:数字中的位数减去9,然后加上9,然后再加上数字。这允许数字最多18位:对我来说足够好了。

我也在以其他方式规范化字符串-一切都要小写,Unicode字符将被翻译成最接近的ASCII等价字符,如果是第一个单词,“a”、“an”和“the”将被剥离。

我放弃了把字符串变成一个大的数值;它仍然是一个字符串,只是它不是为人类设计的。