Many text-editor users depend on spellcheckers to correct their typographical errors. The absence of a spellchecker can create a negative experience for the user. In today's advanced technological environment spellchecking is an expected feature. 2Consiliate Business Solutions owns a Java application with a text-editor which does not have a spellchecker. This project aims to investigate and implement available techniques and algorithms for spellcheckers and automated word correction. During implementation, the techniques were tested for their performance and the best solutions were chosen for this project. All the techniques were gathered from earlier written literature on the topic and implemented in Java using default Java libraries. Analysis of the results proves that it is possible to create a complete spellchecker combining available techniques and that the quality of a spellchecker largely depends on a well defined dictionary.

The evolution in networking coupled with an increasing demand to improve user experience has led to different proposals to extend the standard TCP. Multipath TCP (MPTCP) is one such extension that has the potential to overcome few inherent limitations in the standard TCP. While MPTCP's design and deployment progresses, most of the focus has been on its compatibility. The security aspect is confined to making sure that the MPTCP protocol itself offers the same security level as the standard TCP. The topic of this thesis is to investigate the unexpected security implications raised by using MPTCP in the traditional networking environment. The Internet of today has security middle-boxes that perform traffic analysis to detect intrusions and attacks. Such middle-boxes make use of different assumptions about the traffic, e.g., traffic from a single connection always arrives along the same path. This along with many other assumptions may not be true anymore with the advent of MPTCP as traffic can be fragmented and sent over multiple paths simultaneously. We investigate how practical it is to evade a security middle-box by fragmenting and sending traffic across multiple paths using MPTCP. Realistic attack traffic is used to evaluate such attacks against Snort IDS to show that these attacks are feasible. We then go on to propose possible solutions to detect such attacks and implement them in an MPTCP proxy. The proxy aims to extend the MPTCP performance advantages to servers that only support standard TCP, while ensuring that intrusions can be detected as before. Finally, we investigate the potential MPTCP scenario where security middle-boxes only have access to some of the traffic. We propose and implement an algorithm to perform intrusion detection in such situations and achieve a nearly 90% detection accuracy. Another contribution of this work is a tool, that converts IDS rules into equivalent attack traffic to automate the evaluation of a middle-box. / Multipath TCP (MPTCP) is an extension to standard TCP that is close to being standardized. The design of the protocol is progressing, but most of the focus has so far been on its compatibility. The security aspect is confined to making sure that the MPTCP protocol itself offers the same security level as standard TCP. The topic of this thesis is to investigate the unexpected security implications raised by using MPTCP in a traditional networking environment. Today, the security middleboxes make use of different assumptions that may not be true anymore with the advent of MPTCP.We investigate how practical it is to evade a security middlebox by fragmenting and sending traffic across multiple paths using MPTCP. Realistic attack traffic generated from a tool that is also presented in this thesis is used to show that these attacks are feasible. We then go on to propose possible solutions to detect such attacks and implement them in an MPTCP proxy. The proxy aims to extend secure MPTCP performance advantages. We also investigate the MPTCP scenario where security middleboxes can only observe some of the traffic. We propose and implement an algorithm to perform intrusion detection in such situations and achieve a high detection accuracy. / HITS

This thesis consists of two parts. In part I, a group of combinatorial problems pertaining to strings, boolean matrices and graphs is studied. For given two strings x and y, their edit distance is the minimum number of character insertions, deletions and substitutions required to convert x into y. In this thesis we provide an algorithm that computes a constant approximation of edit distance in truly sub-quadratic time. Based on the provided ideas, we construct a separate sub- quadratic time algorithm that can find an occurrence of a pattern P in a given text T while allowing a few edit errors. Afterwards we study the boolean matrix multiplication (BMM) problem where given two boolean matrices, the aim is to find their product over boolean semi-ring. For this problem, we present two combinatorial models and show in these models BMM requires Ω(n3 /2O( √ log n) ) and Ω(n7/3 /2O( √ log n) ) work respectively. Furthermore, we also give a construction of a sparse sub-graph that preserves the distance between a designated source and any other vertex as long as the total weight increment of all the edges is bounded by some constant. In part II, we study the efficient construction of quasi-Gray codes. We give a construction of space optimal quasi-Gray codes over odd sized alphabets with read complexity 4...

The diploma thesis describes the analysis, specification, origin and transformation of the current editing system N.E.S.P.I, which is the intellectual property of the company WebRex s.r.o. The main aim is to separate the administration of the web sites from their content, which can be seen on the Internet and by doing so to achieve the unified and complex administration interface for the customers. By bringing the service into work we do not only save time and simplify the work of the programmers, but we are also able to reach the stage when the editing system is not only the intellectual property of the company, but also its physical property, because the customer owns only the web sites, but the possibility to administrative them is offered as further service. The service should also provide the customers with modern access to informational technologies and propose enhanced assistance for their entrepreneurial plans and ideals.

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第19336号 / 情博第588号 / 新制||情||103(附属図書館) / 32338 / 京都大学大学院情報学研究科知能情報学専攻 / (主査)教授 阿久津 達也, 教授 山本 章博, 教授 岡部 寿男 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

This master’s thesis project undertook investigation of whether the extant Damerau- Levenshtein edit distance measurement between two strings could be made more useful for detecting and adjusting misspellings in a search query. The idea was to use the knowledge that many users type their queries using the QWERTY keyboard layout, and weighting the edit distance in a manner that makes it cheaper to correct misspellings caused by confusion of nearer keys. Two different weighting approaches were tested, one with a linear spread from 2/9 to 2 depending on the keyboard distance, and the other had neighbors preferred over non-neighbors (either with half the cost or no cost at all). They were tested against an unweighted baseline as well as inverted versions of themselves (nearer keys more expensive to replace) against a dataset of 1,162,145 searches. No significant improvement in the retrieval of search results were observed when compared to the baseline. However, each of the weightings performed better than its corresponding inversion on a p < 0.05 significance level. This means that while the weighted edit distance did not outperform the baseline, the data still clearly points toward a correlation between the physical position of keys on the keyboard, and what spelling mistakes are made. / Detta examensarbete åtog sig att undersöka om det etablerade Damerau-Levenshtein-avståndet som mäter avståndet kan anpassas för att bättre hitta och korrigera stavningsfel i sökfrågor. Tanken var att använda det faktum att många användare skriver sina sökfrågor på ett tangentbord med QWERTY-layout, och att vikta ändrings- avståndet så att det blir billigare att korrigera stavfel orsakade av hopblandning av två knappar som är närmare varandra. Två olika viktningar testades, en hade vikterna utspridda linjärt mellan 2/9 och 2, och den andra föredrog grannar över icke-grannar (antingen halva kostnaden eller ingen alls). De testades mot ett oviktat referensavstånd samt inversen av sig själva (så att närmare knappar blev dyrare att byta ut) mot ett dataset bestående av 1 162 145 sökningar. Ingen signifikant förbättring uppmättes gentemot referensen. Däremot presterade var och en av viktningarna bättre än sin inverterade motpart på konfidensnivå p < 0,05. Det innebär att trots att de viktade distansavstånden inte presterade bättre än referensen så pekar datan tydligt mot en korrelation mellan den fysiska positioneringen av knapparna på tangentbordet och vilka stavningsmisstag som begås.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

No description available.

What do you do if a computational object fails a specification? An obvious approach is to repair it, namely, to modify the object minimally to get something that satisfies the constraints. In this thesis we study foundational problems of repairing regular specifications over strings and trees. Given two regular specifications R and T we aim to understand how difficult it is to transform an object satisfying R into an object satisfying T. The setting is motivated by considering R to be a restriction -- a constraint that the input object is guaranteed to satisfy -- while T is a target -- a constraint that we want to enforce. We first study which pairs of restriction and target specifications can be repaired with a ``small'' numbers of changes. We formalize this as the bounded repair problem -- to determine whether one can repair each object satisfying R into T with a uniform number of edits. We provide effective characterizations of the bounded repair problem for regular specifications over strings and trees. These characterizations are based on a good understanding of the cyclic behaviour of finite automata. By exploiting these characterizations, we give optimal algorithms to decide whether two specifications are bounded repairable or not. We also consider the impact of limitations on the editing process -- what happens when we require the repair to be done sequentially over serialized objects. We study the bounded repair problem over strings and trees restricted to this streaming setting and show that this variant can be characterized in terms of finite games. Furthermore, we use this characterization to decide whether one can repair a pair of specifications in a streaming fashion with bounded cost and how to obtain a streaming repair strategy in this case. The previous notion asks for a uniform bound on the number of edits, but having this property is a strong requirement. To overcome this limitation, we study how to calculate the maximum number of edits per character needed to repair any object in R into T. We formalize this as the asymptotic cost -- the limit of the number of edits divided by the length of the input in the worst case. Our contribution is an algorithm to compute the asymptotic cost for any pair of regular specifications over strings. We also consider the streaming variant of this cost and we show how to compute it by reducing this problem to mean-payoff games.

Henri IV met fin aux guerres civiles de religion en 1598 en décrétant la mémoire des troubles « éteinte et assoupie, comme de chose non advenue ». Comment se positionne le théâtre français par rapport à cette politique d’oubli, quel espace mémoriel offre-t-il ? Nous considérons la tragédie qui s’écrit entre 1629, fin officielle des guerres civiles et date de la dernière tragédie d’actualité, et 1653, fin de la Fronde et d’une nouvelle menace de division intérieure. La tragédie semble se détourner d’une actualité trop déchirante, en ce sens elle oublie, mais elle se trouve pourtant travaillée par cet oublié. En partant du plus visible : la mise en scène des princes cléments, nous montrons que cette forme d’oubli officiel et volontaire est très représentée sur la scène tragique. Mais l’oublié est aussi ce qui travaille les tragédies dans la représentation qu’elles offrent du conflit familial qui fournit bon nombre des sujets tragiques du temps. La tragédie fait donc affleurer le présent du passé, la mémoire de la division, par le détour allégorique. À un théâtre mélancolique où le passé pèse sur le présent de tout son poids s’oppose un théâtre de relance historique dans lequel peut s’ouvrir un avenir nouveau. Enfin, l’oubli apparaît dans ces années de théorisation dramatique comme un idéal pour le spectateur absorbé dans le spectacle, et comme une menace quand il conduit à l’oubli de soi chez certains comédiens ou spectateurs naïfs. L’oubli, dans son équivocité fondamentale, permet donc d’articuler théorie politique, dramatique et images scéniques, dans un premier dix-septième siècle où l’on ne cesse de penser la violence qui menace le lien et la communauté au risque de la division. / Henry the 4th ends the religious civil wars in 1598 by ordaining that the remembrance of troubles is « extinguished and abated, like something that did not occur ». How does French drama stand in relation with this politics of oblivion ? What kind of memorial space does it open ? We consider tragedies written between 1629, official end of the troubles and date of publication of the last usual times tragedy, and 1653, end of a new internal division threat embodied by the Fronde. In appearance, tragedy seems to forget a harrowing recent past by turning away from it, but it is simultaneously deeply influenced by what has been forgotten. By starting with what is most visible, the staging of merciful princes, we demonstrate that this official and voluntary oblivion is very much represented on the tragic stage. But forgetfulness is also influencing tragedies in their displaying of family feuds, a frequent tragic topic of these times. Tragedy thus makes surface the present of the past, the memory of division, through allegoric detours. A double-face drama emerges : one of melancholy in which past weighs on present, one of historical reset with an ouverture for renascent prospects. Last, in these years of dramatic theorization, forgetfulness appears to be, for a spectator absorbed by the play, an ideal, as well as it can drag the most naive of them and some comedians into forgetting about their selves in denial of reality and confusion with fiction. The fundamental ambiguity of forgetfulness enables to articulate political theory, drama and staging, in a 17th century where violence is thought to threaten the community with division.