热门标签 | 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


推荐阅读
  • 本文详细介绍了 Dockerfile 的编写方法及其在网络配置中的应用,涵盖基础指令、镜像构建与发布流程,并深入探讨了 Docker 的默认网络、容器互联及自定义网络的实现。 ... [详细]
  • 数据库内核开发入门 | 搭建研发环境的初步指南
    本课程将带你从零开始,逐步掌握数据库内核开发的基础知识和实践技能,重点介绍如何搭建OceanBase的开发环境。 ... [详细]
  • 使用 Azure Service Principal 和 Microsoft Graph API 获取 AAD 用户列表
    本文介绍了一段通用代码示例,该代码不仅能够操作 Azure Active Directory (AAD),还可以通过 Azure Service Principal 的授权访问和管理 Azure 订阅资源。Azure 的架构可以分为两个层级:AAD 和 Subscription。 ... [详细]
  • DNN Community 和 Professional 版本的主要差异
    本文详细解析了 DotNetNuke (DNN) 的两种主要版本:Community 和 Professional。通过对比两者的功能和附加组件,帮助用户选择最适合其需求的版本。 ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • Splay Tree 区间操作优化
    本文详细介绍了使用Splay Tree进行区间操作的实现方法,包括插入、删除、修改、翻转和求和等操作。通过这些操作,可以高效地处理动态序列问题,并且代码实现具有一定的挑战性,有助于编程能力的提升。 ... [详细]
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • 本文详细介绍了如何在Linux系统上安装和配置Smokeping,以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装,确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]
  • 1.如何在运行状态查看源代码?查看函数的源代码,我们通常会使用IDE来完成。比如在PyCharm中,你可以Ctrl+鼠标点击进入函数的源代码。那如果没有IDE呢?当我们想使用一个函 ... [详细]
  • 主要用了2个类来实现的,话不多说,直接看运行结果,然后在奉上源代码1.Index.javaimportjava.awt.Color;im ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 本文详细介绍了如何构建一个高效的UI管理系统,集中处理UI页面的打开、关闭、层级管理和页面跳转等问题。通过UIManager统一管理外部切换逻辑,实现功能逻辑分散化和代码复用,支持多人协作开发。 ... [详细]
  • 本文探讨了如何在模运算下高效计算组合数C(n, m),并详细介绍了乘法逆元的应用。通过扩展欧几里得算法求解乘法逆元,从而实现除法取余的计算。 ... [详细]
  • This document outlines the recommended naming conventions for HTML attributes in Fast Components, focusing on readability and consistency with existing standards. ... [详细]
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社区 版权所有