第ｌＯ卷第４期２０１０年２月 科学技术与工・程 Ｖｏ１．１０ Ｎｏ．４ Ｆｅｂ．２０１０ １６７１—１８１５（２０１０）４—１０４１－０４ Ｓｃｉｅｎｃｅ Ｔｅｃｈｎｏｌｏｇｙ ａｎｄ Ｅｎ￣ｎｅｅｆｉｎｇ ＠２０１０ Ｓｃｉ．Ｔｅｃｈ．Ｅｎｇｎｇ． 基于压缩存储的稀疏矩阵转置算法研究 王敏 （渭南师范学院计算机科学系，渭南７１４０００） 摘要介绍了对稀疏矩阵进行压缩存储的几种存储方式，重点分析了稀疏矩阵的三元组压缩存储的不同存储结构，提出利 嗣数组首下标元素存储稀疏矩阵总行数、总列数和非零元素总个数三个信息的改进的三元组顺序表存储定义方式，同时给出 了用Ｃ语言编写的基于该定义上设计矩阵转置的几种算法。通过对各算法进行时间复杂度分析，总结出了几种算法的优 缺点。 关键词稀疏矩阵 压缩存储 三元组表 矩阵转置 时问复杂度 巾图法分类号ＴＰ３１１．１２； 文献标志码Ａ 计算机中存储矩阵的一般方法是采用二维数 组，其优点是可以随机地访问每一个元素，从而易于 实现矩阵的各种运算¨Ｊ。但对于稀疏矩阵（设ｍ Ｘ ｎ １稀疏矩阵的三元组表存储结构 对矩阵的操作可归根结底为对矩阵元素的定位 的矩阵中有ｚ个不为０的元素，令 ＝÷ｍ ，￡ ，称 为 和修改两大类，这两类操作都是根据给定的一组行 列值进行元素的访问。首先分析一下采用压缩存储 的稀疏矩阵中非零元素三元组的抽象数据类型（Ａｂ— ｓｔｒａｃｔ Ｄａｔａ Ｔｙｐｅ）：可将各非零元素三元组按照“行序 为主、列序为辅”的顺序排成一个序列，则在该序列 矩阵的稀疏因子，通常认为６≤０．０５时为稀疏矩 阵 ）来说，大量零元素的存储会造成存储空间的 浪费。为了在实现矩阵相关操作时提高存储空间的 利用率，需要对稀疏矩阵进行有效的压缩存储，即只 存储矩阵中的非零元素。由于稀疏矩阵中的非零元 素分布没有规律，要实现压缩存储，则记录每个非零 中，除了首尾以外的其余三元组都只有唯一的前驱 和后继。显然，这构成一种线性逻辑结构，可采用顺 序和非顺序两种存储方式，具体采用哪种主要取决 于将设计实现矩阵的哪些操作。非顺序存储方式主 要采用链式存储结构（比如十字链表），适用于设计 实现对稀疏矩阵的非零元素个数有改变的一类操作 （比如矩阵相加、相减、相乘等）；而对于矩阵转置之 类非零元素个数不变的操作，则采用顺序存储结构 （比如一维数组）实现较为方便，即三元组顺 元素的元素值的同时，还必须给出其所在行、列的下 标位置，构成形如（ＦＯＷ，ｃｏｌｕｍｎ，ｖａｌｕｅ）的非零元素 三元组。 本文将重点研究稀疏矩阵采用三元组表压缩存 储方式的改进办法，给出改进后用Ｃ语言编写的几 种不同的稀疏矩阵转置算法，通过对各个算法进行 时间复杂度分析，总结比较出各个算法的优缺点。 序表 引。 稀疏矩阵的存储信息还应包括矩阵总行数、矩 ２００９年ｌ１月１０日收到 作者简介：王件算法一 国家自然科学基金（６０８０３１３２）资助 阵总列数和矩阵中非零元素的总个数。大多数参考 文献中关于稀疏矩阵存储结构的定义均额外定义了 敏（１９７２一），陕西临潼人，讲师，硕士，研究方向：软 用于存储这三方面信息的结构体成员变量，而这种 １０４２ 科学技术与工程 ｌ０卷 存储处理其实可以进行简化：由于前述三种信息的 类型同三元组的各个成员类型相兼容，因此可将三 元组向量的首下标单元的对应三元分别用于存放这 三方面信息。三元组顺序表存储结构的稀疏矩阵可 使用Ｃ语言定义如下： ＃ｄｅｆｔｎｅ ＭＡＸ １０００ 。ｔｙｐｅｄｅｆ ｓｔｒｕｃｔ｛ ｉｎｔ ｒ０ｗ．ｃｏｌ； Ｅｌｅｍｔｙｐｅ ｖａｌ； ｝Ｔｒｉｐｌｅ［ ］； ｔｙｐｅｄｅｆ Ｔｒｉｐｌｅ ＴＳＭａｍｘ［ ］［ＭＡＸ］； 由于矩阵的行列编号一般从１起始，因而可将 Ｃ语言数组的０下标单元用于存储前述三种信息。 ２矩阵转置操作的算法比较 基于三元组顺序表存储结构实现矩阵转置的算 法可归纳为直接转置、根据转置矩阵的行序进行转 置和快速转置三种。下面将待转置矩阵记作Ａ（ 行Ⅳ列），转置矩阵记作Ｂ（Ⅳ行 列），分别对几种 算法加以分析讨论。 ２．１直接转置算法 该算法的第一步直接将矩阵Ａ的非零元素三元 组的行列互换后赋值给转置矩阵Ｂ；为了保证矩阵 Ｂ仍然是以“行序为主序”存放，该算法还需要进一 步对 矩阵中的三元组进行按行排序。 执行第一步时，算法的基本语句是实现三元组 赋值操作的循环体语句，因而此部分算法的时间复 杂度取决于矩阵中的非零元素三元组的个数（视为 问题的规模乃），即 （ｎ）＝０（凡）；执行第二步时，算 法的时间复杂度既同问题的规模ｎ相关，又取决于 所采用的排序算法，且排序过程中将有三元组的移 动操作。例如采用快速排序算法时该部分的平均时 间复杂度 （ｎ）＝０（凡×Ｉｇ：ｎ），这样，两步操作总的 时间复杂度为 （ｎ）＝ＴＩ（ｎ）＋ （ｎ）＝ ０（ｎ＋ｎ×Ｉｇ２ｎ），即Ｔ（ｎ）＝Ｏ（凡×Ｉｇ２ｎ）。 ２．２根据转置矩阵的行序进行转置的算法 该算法是在矩阵Ａ的三元组表中按照转置矩阵 日的行序（即矩阵Ａ的列序），逐一将Ａ的三元组行 列互换并赋值给Ｂ的转置操作。基于前述存储类型 ＴＳＭａｔｒｉｘ的算法可用Ｃ语言描述如下： ｖｏｉｄ ＴｒａｎｓｐｏｓｅＭａｔｒｉｘ（ＴＳＭａｔｒｉｘ Ａ，ＴＳＭａｔｒｉｘ Ｂ） ｛ｉｎｔ ｉ，ｊ， ； ／／ｉ为Ａ的三元组表下标，ｊ为Ｂ的三元组表下标 （ Ｂ）［Ｏ］．１０Ｗ＝Ａ［０］．ｃｏｌ； （｝Ｂ）［Ｏ］．ｃｏｌ＝Ａ［０］．ｒｏｗ； （ Ｂ）［０］．ｖａｌ＝Ａ［Ｏ］．ｖａｌ； ｉｆ（Ａ［Ｏ］．ｖ￣）／／有非零元素三元组则进行转置 ｛ ｆｏｒ（ｊ＝１，ｒ＝１；ｒ＜＝（｝Ｂ）［ｏ ３．ｒｏｗ；ｒ＋＋） ／／根据Ｂ的行逐行进行转置 ｆｏｒ（ｉ＝１；ｉ＜＝Ａ［０］．ｖａｌ；ｉ＋＋） ｛ｉｆ（Ａ［ｉ］．ｃｏｌ＝＝ｒ） ／／当Ａ中三元组的列号为正在查找的行时进行转置 ｛（女Ｂ）［ｊ］．１ｏｗ＝ ； （十Ｂ）［ｊ］．ｃｏｌ＝Ａ［ｉ］．１ｏｗ； （｝Ｂ）［ｊ］．ｖａｌ＝Ａ［ｉ］．ｖａｌ； ｊ＋＋； ｝ ｝ ｝Ｉ 程序中的基本语句是双重循环的循环体语句， 因而算法的时间复杂度取决于转置矩阵Ｂ的总行数 Ⅳ和矩阵中非零元素三元组的个数 ０］．ｖａｌ（即前 述问题的规模ｎ），从而算法的时间复杂度 为 （凡）＝Ｄ（Ｎ×ｎ）。 ２．３快速转置算法 快速转置算法是依次将待转置矩阵Ａ的三元组 行列互换后，直接放到转置矩阵 的三元组表中的 正确位置。该算法需考虑两个因素：一是矩阵Ａ每 列中非零元素的个数（即转置矩阵日每一行中非零 元素的个数）；二是矩阵Ａ各列中第一个非零元素三 元组在 中的正确位置（即矩阵曰各行中第一个非 零元素三元组在Ｂ中的正确位置）。为此，可设置 两个数组ｒｇｕｍ［］和ｐｏｓｉｔｉｏｎ［］，前者用来存放 中 第ｃｏｚ列（Ｂ中第ｃ０ｚ行）的非零元素个数，后者用以 存放Ａ中第ｃｏｌ列（Ｂ中第ｃｏｌ行）中第一个非零元 素在三元组表Ｂ中的正确位置 。 计算ｌｚｕｍ［ｃｏ１］可通过一遍对矩阵Ａ的三元组 表的循环扫描，将其中列号为ｃ０Ｚ的元素的对应 ｎｌｚｍ［ｃｏ１］加１；而ｐｏｓｉｔｉｏｎ［ｃｏ１］可通过如下公式计算： ４期 王敏：基于压缩存储的稀疏矩阵转置算法研究 １０４３ ｐｏｓｉｔｉｏｎ［ｃｏ１］ ｆｌ （ｃｏｌ＝１）； 因而算法总的时间复杂度为Ｔ（凡）＝０（Ｎ＋ｎ）。 ｍ［ｃ０ｆ＿１］ ｔｉ ｏｎ［ｃｏｌ －１］ （１＜ｃｏｌ＜Ａ［０］．ｃｏ１）。 得到上述两个数组的对应值后，要将Ａ中的三 元组直接放到Ｂ中的正确位置，可利用ｐｏｓｈｉｏｎ数组 ３结论 在对矩阵采用三元组顺序表压缩存储技术时， 由于需要同时保存矩阵的总行数和总列数，另外为 实现：ｐｏｓｉｔｉｏｎ［ｃｏ１］的初值为矩阵Ａ的三元组表中第 ｃｏｚ列（日中第ｃｏｚ行）的第一个非零元素三元组在 了便于三元组顺序表的操作，还需保存非零元素三 中的正确位置，当Ａ中第ｃ０ｚ列有一个元素加入三元 组表Ｂ时，则ｐｏｓｉｔｏｉｎ［ｃ０ｚ］的值加１，即：使 ｐｏｓｉｔｏｉｎ［ｃｏ１］始终指向三元组表Ａ中第ｃ０ｚ列中下一 个非零元素在三元组表曰中的正确位置 引。基于 前述存储类型ＴＳＭａｔｒｉｘ的Ｃ： ｖｏｉｄ ＦａｓｔＴｒａｎｓＭａｔｒｉｘ（ＴＳＭａｔｒｉｘ Ａ，ＴＳＭａｔｒｉｘ Ｂ） ｛ｉｎｔ ｃｏｌ，ｉ，ｊ；／／ｃｏｌ作为辅助数组下标 ／／ｉ指示矩阵Ａ的三元组表下标，ｊ指示Ｂ的三元组表下标 ｉｎｔ ｎｕｍ［ＭＡＸ］，ｐｏｓｉｔｉｏｎ［ＭＡＸ］； （ Ｂ）［０】．１０Ｗ：Ａ［０］．ｃｏｌ； （＋Ｂ）［０］．ｃｏｌ＝Ａ［Ｏ］．ｒｏｗ； （ Ｂ）［ｏ］．ｖａｌ＝Ａ［Ｏ］．ｖａｌ； ｉｆ（Ａ［０］．ｖ８Ｊ） ／／有非零元素三元组则进行转置 ｛ｆｏｒ（ｃｏｌ＝１；ｃｏｌ＜＝Ａ［０］．ｃｏｌ；ｒ＋＋） ｎｕｍ［ｃｏ１］：０； ／／矩阵Ａ各列非零元素个数计数预置为０ ｆｏｒ（ｉ＝１；ｉ＜：Ａ［０］．ｖａｌ；ｒ＋＋） ｈｕｍ［Ａ［ｉ］．ｃｏ１］＋＋； ／／矩阵Ａ各列非零元素个数计数 ｐｏｓｉｔｉｏｎ［１］＝１； ｏｆｒ（ｃｏｌ＝２；ｃｏｌ＜＝Ａ［０］．ｃｏｌ；ｃｏｌ＋＋） ／／求ｃｏｌ列中第一个非零元素三元组在Ｂ中的正确位置 ｐｏｓｉｔｉｏｎ［ｃｏ１］＝ｐｏｓｉｔｉｏｎ［ｃｏｌ—ｉ］＋ｎｕｍ［ｃｏｌ一１］； ｆｏｒ（ｉ＝１；ｉ＜：Ａ［Ｏ］．ｖａｌ；ｉ＋＋） ／／对矩阵Ａ的三元组表扫描一遍完成转置 ｛Ｊ＝ｐｏｓｉｔｉｏｎ［Ａ［ｉ］．ｃｏ１］； （ Ｂ）［Ｊ］．ＩＯＷ＝Ａ［ｉ］．ｃｏｌ； （ Ｂ）［ｊ］．ｃｏｌ：Ａ［ｉ］．１ＯＷ； （ Ｂ）［ｊ】．ｖａｌ＝Ａ［ｉ］．ｖａｌ； ｐｏｓｉｔｉｏｎ［ｃｏ１］＋ ；｝ ｝｝ 该算法程序由前后四个循环部分组成，各个循 环的基本语句分别执行了Ａ［０］．ｃｏｌ、Ａ［Ｏ］．ｖａｌ、Ａ ［０］．ｃ０ｌ—ｌ和Ａ［０］．ｖａ１次，其中Ａ［０］．ｖａｌ即前述 问题的规模ｎ，Ａ［０］．ｃｏｌ也即转置矩阵的总行数Ⅳ， 元组的总个数，本文给出了利用三元组表向量首下 标单元存储这些信息的存储方案，并给出了对应的 Ｃ语言结构定义ＴＳＭａｍｘ，这就省去了另外再定义这 些结构体成员变量的麻烦。 本文给出的算法的Ｃ语言程序均已上机测试通 过。通过对比分析三种算法的时间复杂度，可得到 以下结论： 快速转置算法的平均时间复杂度最低。对于直 接转置的方法～和按转置矩阵Ｂ的行序进行转置的 方法二来说，当问题的规模ｎ较小时，ｌｏｇ：１３也较小， 因而此时方法一的时间复杂度较低，但方法一在对 矩阵Ｂ中的三元组进行按行排序时要涉及元素的移 动，算法的实际执行效率会有所降低。另外，随着问 题的规模ｎ的增大，即非零元素个数接近矩阵的行 列之积（Ｍ×Ｎ）时，则方法一的时间复杂度接近 ０（Ｍ×Ｎ×ｌｏｇ （Ｍ×Ｎ）），方法二的时间复杂度接近 Ｄ（Ｍ×Ｎ２），均不如非压缩存储的经典双重循环算 法（其时间复杂度为 （ｎ）＝０（Ｍ×Ⅳ））；而此时快 速转置算法的时间复杂度接近０（Ｍ×Ｎ）。 稀疏矩阵的三元组表压缩存储结构虽然节约了 存储空间，但同普通的矩阵存储方式比较，增加了实 现相同操作的算法设计难度。另外随着非零元素个 数的增加，算法的时间效率也逐渐降低。可见，前两 种算法从某种程度上说是以时间为代价换取了空间 的节省。快速转置算法虽然在时间效率上较前两种 算法有所提高，但在空间上除了三元组表所占空间 外，还需要增加辅助向量ｎｌｇｍ［Ⅳ］和ｐｏｓｉｔｏｉｎ［Ⅳ］的 空间，则又是以空间为代价换取了时间的节省。可 见，算法的运行时间、所占的存储空间以及算法设计 的简单性往往是相互矛盾的，因而在设计时仍需要 根据实际情况加以权衡。 １０４４ 科学技术与工程 １０卷 ２严蔚敏，吴伟民．数据结构．北京：清华大学出版社，２０００：９６，９８ 参考文献 ３耿国华．数据结构．Ｃ语言描述．西安：西安电子科技大学出版 社。２００６：１Ｏ１一ｌ０４ １徐孝凯．数据结构简明教程．北京：清华大学出版社，１９９５：７１ Ｓｔｕｄｙ Ｏｉｌ ｔｈｅ Ｓｐａｒｓｅ Ｍａｔｒｉｘ Ｔｒａｎｓｐｏｓｅ Ａｌｇｏｒｉｔｈｍｓ Ｂａｓｅｄ Ｏｉｌ Ｃｏｍｐｒｅｓｓｅｄ Ｓｔｏｒａｇｅ ＷＡＮＧ Ｍｉｎ （Ｗｅｉｎａｎ Ｔｅａｃｈｅｒｓ Ｕｎｉｖｅｒｓｉｔｙ，Ｗｅｉｎａｎ ７１４０００，Ｐ．Ｒ．Ｃｈｉｎａ） 『Ａｂｓｔｒａｃｔ］ Ｓｅｖｅｒａｌ ｃｏｍｐｒｅｓｓｉｏｎ ｓｔｏｒａｇｅ ｍｅｔｈｏｄｓ ｏｆ ｔｈｅ ｓｐａｒｓｅ ｍａｔｒｉｘ ａｒｅ ｄｅｓｃｒｉｂｅｄ ａｎｄ ｆｏｃｕｓｅｄ ｏｎ ａｎａｌｙｓｉｓ ｏｆ ｄｉｆ－ ｆｅｒｅｎｔ ｃｏｍｐｒｅｓｓｉｏｎ ｓｔｏｒａｇｅ ｔｅｃｈｎｏｌｏｇｙ ａｂｏｕｔ ｔｈｅ ｔｒｉｐｌｅ ｌｉｓｔ ｆ０ｒ ｔｈｅ ｓｐａｒｓｅ ｍａｔｒｉｘ．Ａｆｔｅｒ ｄｅｓｃｒｉｂｉｎｇ ｔｈｅ ｃｏｍｐｒｅｓｓｉｏｎ ｓｔｏｒａｇｅ ｄｅｆｉｎｉｔｉｏｎ ａｂｏｕｔ ｔｈｅ ｔｒｉｐｌｅ ｌｉｓｔ ０ｆ ｔｈｅ ｓｐａｒｓｅ ｍａｔｒｉｘ．ａｎ ｉｍｐｒｏｖｅｄ ｓｔｏｒａｇｅ ｄｅｆｉｎｉｎｇ ｍｅｔｈｏｄ ｉｓ ｐｕｔ ｆｏｒｗａｒｄ ｔｏ ｕｓｅ ａｎ ａｒｒａｖ ｅｌｅｍｅｎｔ ｉｎ ｔｈｅ ｆｉｒｓｔ ｓｕｂｓｃｒｉｐｔ ｏｆ ｔｈｅ ｓｅｑｕｅｎｃｅ ｔｒｉｐｌｅ ｌｉｓｔ ａｒｒａｙ ｔｏ ｄａｃｌａｒｅ ｔｈｅ ｉｎｆｏｒｍａｔｉｏｎ ａｂｏｕｔ ｔｈｅ ｔｏｔｌ ｎｎｍ ａｂｅｒ ｏｆ ｒｏｗｓ．ｔｈｅ ｔｏｔａｌ ｎｕｍｂｅｒ ｏｆ ｃｏｌｕｍｎｓ ａｎｄ ｔｈｅ ｔｈｅ ｔｏｔａｌ ｎｕｍｂｅｒ ｏｆ ｎｏｎ—ｚｅｒｏ ｅｌｅｍｅｎｔｓ ｏｆ ｔｈｅ ｓｐａｒｓｅ ｍａｔｉｒｘ，ａｎｄ ｈｅｎ ｓｔａｖｅｓ ｔｈｅ ｍａｔｒｉｘ ｔｒａｎｓｐｏｓｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｗｒｉｔｔｅｎ ｉｎ Ｃ ｐｏｇｒａｍ ｌａｎｇｕａｇｅ ｂａｓｅｄ ０ｎ ｔｈｅ ｄｅｆｉｎｉｔｉｏｎ ｐｒｏｐｏｓｅｄ．Ｂｙ ａｎａ ｌｙｚｉｎｇ ｔｈｅ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｓｅｖｅｒａｌ ｓｐａｒｓｅ ｍａｔｒｉｘ ｔｒａｎｓｐｏｓｉｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ，ｗｈｉｃｈ ｂａｓｅｄ ｏｎ ｔｈｅ ｃｏｍｐｒｅｓｓｉｏｎ ｓｔｏｒａｇｅ ｓｔｎｃｔｉｕｒｅ ｄｉｃｕｓｓｅｄ ｈｅｒｅ，ｔｈｅ ａｄｖａｎｔａｇｅｓ ａｎｄ ｄｉｓａｄｖａｎｔａｇｅｓ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍｓ ｄｉｓｃｕｓｓｅｄ ａｒｅ ｓｕｍｍａｒｉｚｅｄ． ［Ｋｅｙ ｗｏｒｄｓ］ ｓｐａｒｓｅ ｍａｔｒｉｘ 、 、 ｃｏｍｐｒｅｓｓｅｄ ｓｔｏｒａｇｅ ｔｉｒｐｌｅ ｌｉｓｔ ｒｔａｎｓｐｏｓｅ ｍａｔｉｒｘ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ （上接第１０４０页） Ｒｅｓｅａｒｃｈ ａｂｏｕｔ Ｓｏｆｔｗａｒｅ Ｓｙｓｔｅｍ Ｓｉｚｅ Ｅｓｔｉｍａｔｉｏｎ ｂｙ Ｉｔｅｒａｔｉｏｎ Ｄｅｖｅｌｏｐｍｅｎｔ ＬＩＮ Ｆａｎｇ （１）ｅｌ，ａｌｌ『ｌｌｅｎｔ ｏｆＣｏｍｐｕｔｅｒ ａｎｄＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅ，Ｊｏｕｒｎａｌ ｏｆＦｕｊｉａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆＴｅｃｈｎｏｌｏｇｙ，Ｆｕｚｈｏｕ ３５００１４，Ｐ．Ｒ．Ｃｈｉｎａ） 『Ａｂｓｔｒａｃｔ］ ＲＵＰ ｄｅｖｅｌｏｐｍｅｎｔ ｐｒｏｃｅｓｓ ｉｓ ｔｈｅ ｍａｉｎｓｔｒｅａｍ ｏｆ ｍｏｄｅｍ ｓｏｆｔｗａｒｅ ｄｅｖｅｌｏｐｍｅｎｔ ｗｉｔｈ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｉｔ— ｅＨｌｔｉ０＿ｎ ａｎｄ ｕｓｅ ｃａｓｅ ｄｒｉｖｅｎ．ＵＣＰ ｂａｓｅｄ ｏｎ ｔｈｅ ｕｓｅ ｃａｓｅ ｉｓ ａ ｓｏｆｗａｒｅ ｔｓｉｚｅ ｅｓｔｉｍａｔｉｏｎ ｔｅｃｈｎｉｑｕｅ．Ｔｈｅ ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ＲＵＰ ｉｓ ｐｒａｃｔｉｃｅｄ，ａｎｄ ｒｅｓｅａｒｃｈ ｂｏｕｔａ ｓｏｆｔｗａｒｅ ｓｙｓｔｅｍ ｓｉｚｅ ｅｓｔｉｍａｔｉｏｎ．Ｆｉｓｒｔ ｅｓｔｉｍａｔｅｓ ｉｔｅｒａｔｉｏｎ ｎｕｍｂｅｒｓ，ｓｅｃｏｎｄ ｅｓｔｉ・ ｍａｔｅｓ ｔｈｅ ｕｓｅ ｃａｓｅ ｐｏｉｎｔｓ ｅａｃｈ ｉｔｅｒａｔｉｏｎ ｂｙ ＵＣＰ，ｗｈｉｃｈ ｉｎｃｌｕｄｅ ｄｅｖｅｌｏｐｉｎｇ ｔｈｅ ｎｅｗ ａｐｐｌｉｃａｔｉｏｎｓ ａｎｄ ｍｏｄｉｆｙｉｎｇ ｔｈｅ ｏｌｄ ａｐｐｌｉｃａｔｉｏｎｓ．Ｔｈｅ ｓｉｚｅ ｏｆ ｔｏｔｌ ｓａｏｆｗａｒｔｅ ｓｙｓｔｅｍ．Ｆｉｎａｌｌｙ ｉｓ ｅｓｔｉｍａｔｅｄ． ［Ｋｅｙ ｗｏｒｄｓ］ ＲＵＰ ＵＣＰ ｓｉｚｅ ｅｓｔｉｍａｔｉｏｎ ＵＭＬ ｉｔｅｒａｔｉｏｎ
