热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

反转移动到前方变换

反转移动到前方变换原文:https://www.geeksf

反转移动到前方变换

原文:https://www . geeksforgeeks . org/reving-move-front-transform/

先决条件: 移动到前方数据变换算法

MTF 变换逆运算背后的主要思想:

1.计算 MTF 变换的逆就是撤销 MTF 变换,恢复原始字符串。我们有“input _ arr”“n”,前者是 MTF 变换,“input _ arr”中的元素数量。

2.我们的任务是维护一个有序的字符列表(在我们的例子中是 a 到 z),并从“input _ arr”中一次读入一个“ith”元素。

3.然后,以该元素为索引 j ,在列表中打印“jth”字符。

Illustration for "[15 1 14 1 14 1]"
List initially contains English alphabets in order.
We move characters at indexes depicted by input
to front of the list one by one.
input arr chars output str list
15 p abcdefghijklmnopqrstuvwxyz
1 pa pabcdefghijklmnoqrstuvwxyz
14 pan apbcdefghijklmnoqrstuvwxyz
1 pana napbcdefghijklmoqrstuvwxyz
14 panam anpbcdefghijklmoqrstuvwxyz
1 panama manpbcdefghijkloqrstuvwxyz

示例:

Input : arr[] = {15, 1, 14, 1, 14, 1}
Output : panama
Input : arr[] = {6, 5, 0, 10, 18, 8, 15, 18,
6, 6, 0, 6, 6};
Output : geeksforgeeks

下面是上面解释的 idea 代码:

// C program to find Inverse of Move to Front
// Transform of a given string
#include
#include
#include
// Takes index of printed character as argument
// to bring that character to the front of the list
void moveToFront(int index, char *list)
{
    char record[27];
    strcpy(record, list);
    // Characters pushed one position right
    // in the list up until index
    strncpy(list+1, record, index);
    // Character at index stored at 0th position
    list[0] = record[index];
}
// Move to Front Decoding
void mtfDecode(int arr[], int n)
{
    // Maintains an ordered list of legal symbols
    char list[] = "abcdefghijklmnopqrstuvwxyz";
    int i;
    printf("\nInverse of Move to Front Transform: ");
    for (i = 0; i     {
        // Printing characters of Inverse MTF as output
        printf("%c", list[arr[i]]);
        // Moves the printed character to the front 
        // of the list
        moveToFront(arr[i], list);
    }
}
// Driver program to test functions above
int main()
{
    // MTF transform and number of elements in it.
    int arr[] = {15, 1, 14, 1, 14, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    // Computes Inverse of Move to Front transform
    // of given text
    mtfDecode(arr, n);
    return 0;
}

输出:

Inverse of Move to Front Transform: panama

时间复杂度: O(n^2)

练习:在一个程序中一起实现 MTF 编码和解码,检查原始消息是否恢复。

来源:
http://www . cs . Princeton . edu/courses/archive/fall 07/cos226/assignments/burrows . html


推荐阅读
  • SQLite数据库CRUD操作实例分析与应用
    本文通过分析和实例演示了SQLite数据库中的CRUD(创建、读取、更新和删除)操作,详细介绍了如何在Java环境中使用Person实体类进行数据库操作。文章首先阐述了SQLite数据库的基本概念及其在移动应用开发中的重要性,然后通过具体的代码示例,逐步展示了如何实现对Person实体类的增删改查功能。此外,还讨论了常见错误及其解决方法,为开发者提供了实用的参考和指导。 ... [详细]
  • HTML 页面中调用 JavaScript 函数生成随机数值并自动展示
    在HTML页面中,通过调用JavaScript函数生成随机数值,并将其自动展示在页面上。具体实现包括构建HTML页面结构,定义JavaScript函数以生成随机数,以及在页面加载时自动调用该函数并将结果呈现给用户。 ... [详细]
  • 本文介绍了如何在iOS平台上使用GLSL着色器将YV12格式的视频帧数据转换为RGB格式,并展示了转换后的图像效果。通过详细的技术实现步骤和代码示例,读者可以轻松掌握这一过程,适用于需要进行视频处理的应用开发。 ... [详细]
  • 动态壁纸 LiveWallPaper:让您的桌面栩栩如生(第二篇)
    在本文中,我们将继续探讨如何开发动态壁纸 LiveWallPaper,使您的桌面更加生动有趣。作为 2010 年 Google 暑期大学生博客分享大赛 Android 篇的一部分,我们将详细介绍 Ed Burnette 的《Hello, Android》第三版中的相关内容,并分享一些实用的开发技巧和经验。通过本篇文章,您将了解到如何利用 Android SDK 创建引人入胜的动态壁纸,提升用户体验。 ... [详细]
  • FastDFS Nginx 扩展模块的源代码解析与技术剖析
    FastDFS Nginx 扩展模块的源代码解析与技术剖析 ... [详细]
  • 本文深入解析了HTML框架集(FRAMESET)的使用方法及其应用场景。首先介绍了几个关键概念,如如何通过FRAMESET标签将主视图划分为多个独立的区域,每个区域可以加载不同的HTML文件。此外,还详细探讨了FRAMESET在实际开发中的优缺点,并提供了具体的实例代码,帮助开发者更好地理解和应用这一技术。 ... [详细]
  • 具备括号和分数功能的高级四则运算计算器
    本研究基于C语言开发了一款支持括号和分数运算的高级四则运算计算器。该计算器通过模拟手算过程,对每个运算符进行优先级标记,并按优先级从高到低依次执行计算。其中,加减运算的优先级最低,为0。此外,该计算器还支持复杂的分数运算,能够处理包含括号的表达式,提高了计算的准确性和灵活性。 ... [详细]
  • 在本文中,我们将为 HelloWorld 项目添加视图组件,以确保控制器返回的视图路径能够正确映射到指定页面。这一步骤将为后续的测试和开发奠定基础。首先,我们将介绍如何配置视图解析器,以便 SpringMVC 能够识别并渲染相应的视图文件。 ... [详细]
  • 本文探讨了如何利用 jQuery 的 JSONP 技术实现跨域调用外部 Web 服务。通过详细解析 JSONP 的工作原理及其在 jQuery 中的应用,本文提供了实用的代码示例和最佳实践,帮助开发者解决跨域请求中的常见问题。 ... [详细]
  • 本文总结了JavaScript的核心知识点和实用技巧,涵盖了变量声明、DOM操作、事件处理等重要方面。例如,通过`event.srcElement`获取触发事件的元素,并使用`alert`显示其HTML结构;利用`innerText`和`innerHTML`属性分别设置和获取文本内容及HTML内容。此外,还介绍了如何在表单中动态生成和操作``元素,以便更好地处理用户输入。这些技巧对于提升前端开发效率和代码质量具有重要意义。 ... [详细]
  • 本文探讨了利用JavaScript实现集合的对称差集算法的方法。该算法旨在处理多个数组作为输入参数,同时保留每个数组中元素的原始顺序。算法不会移除单个数组内的重复元素,但会删除在不同数组之间出现的重复项。通过这种方式,能够有效地计算出多个数组的对称差集。 ... [详细]
  • 2012年9月12日优酷土豆校园招聘笔试题目解析与备考指南
    2012年9月12日,优酷土豆校园招聘笔试题目解析与备考指南。在选择题部分,有一道题目涉及中国人的血型分布情况,具体为A型30%、B型20%、O型40%、AB型10%。若需确保在随机选取的样本中,至少有一人为B型血的概率不低于90%,则需要选取的最少人数是多少?该问题不仅考察了概率统计的基本知识,还要求考生具备一定的逻辑推理能力。 ... [详细]
  • 2014年3月16日 长沙多所高校联合举办第三次学术交流活动
    2014年3月16日,长沙多所高校联合举办了第三次学术交流活动。此次活动旨在促进各高校间的学术合作与交流,吸引了众多师生参与。交流内容涵盖了计算机科学、工程技术等多个领域,为参会者提供了丰富的学习和讨论机会。 ... [详细]
  • 本文详细介绍了如何安全地手动卸载Exchange Server 2003,以确保系统的稳定性和数据的完整性。根据微软官方支持文档(https://support.microsoft.com/kb833396/zh-cn),在进行卸载操作前,需要特别注意备份重要数据,并遵循一系列严格的步骤,以避免对现有网络环境造成不利影响。此外,文章还提供了详细的故障排除指南,帮助管理员在遇到问题时能够迅速解决,确保整个卸载过程顺利进行。 ... [详细]
  • 在HTML5应用中,Accordion(手风琴,又称抽屉)效果因其独特的展开和折叠样式而广泛使用。本文探讨了三种不同的Accordion交互效果,通过层次结构优化信息展示和页面布局,提升用户体验。这些效果不仅增强了视觉效果,还提高了内容的可访问性和互动性。 ... [详细]
author-avatar
x75066882
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有