基于 Spark 的大规模网络流量准实时分类方法

大数据时代催生了互联网流量的指数级增长,为了有效地管控网络资源,提高网络安全性,需要对网络流量进行快速、准确的分类,这就对流量分类技术的实时性提出了更高的要求。目前,国内外的网络流量分类研究大多是在单机环境下进行的,计算资源有限,难以应对高速网络中的 (准) 实时流量分类任务。本文在充分借鉴已有研究成果的基础上,吸收当前最新的思想和技术,基于Spark 平台,有机结合其流处理框架 Spark Streaming 与机器学习算法库 MLlib,提出一种大规模网络流量准实时分类方法。实验结果表明,该方法在保证高分类准确率的同时,也具有很好的实时分类能力,可以满足实际网络中流量分类任务的实时性需求。     

Image theorems for simple matrix languages andn-parallel languages

Three image theorems are proved for three families of languages in terms of prototype languages and (nondeterministic) generalized sequential machine maps. Further, for one family, then-right linear simple matrix languages of Ibarra, a new characterization theorem is proved.Work carried out under a National Research Council of Canada Grant No. A-7700.     

Ergodic languages

We present here a new way of defining languages via rewriting systems, and study the obtained families of languages, and their relationship to Chomsky hierarchy.     

有向图语言

经典形式语言有两条主线,就是自动机线索与形式文法线索。利用有向图理论和有向图半群理论建立了另一条线索——有向图语言,讨论了两类特殊的有向图语言——de Bruijn有向图语言和Kautz有向图语言,引入了连通语言及语言的直径等概念,计算出了de Bruijn有向图语言和Kautz有向图语言的直径。     

Multi-stack-counter languages

A stack-counter acceptor is a stack acceptor in which the storage alphabet is just one letter. The present paper discusses multi-stack-counter acceptors operating in quasirealtime, i.e., acceptors in which each storage tape is a stack counter and in which there are only a bounded number of consecutive-moves. For each positive integerk let be the family of languages accepted byk-stack-counter acceptors (k-counter acceptors). Each is a principal AFL closed under reversal but not under-free substitution or under intersection. Also, and a specific language in each, is exhibited. For each and there are noi andj such that. It is shown that a quasi-real-timek-stackcounter acceptor is equivalent to one operating in non-deterministic real time. Lastly, it is shown that acceptance by final state of ak-stack-counter acceptor is equivalent to acceptance by empty tape and final state.Also formerly with System Development Corporation, Santa Monica, California. Research sponsored in part by the Air Force Cambridge Research Laboratories, Office of Aerospace Research, USAF, under Contract F19628-70-C-0023; by the Air Force Office of Scientific Research, Office of Aerospace Research, USAF, under AFOSR No. F44620-70-C-0013; and by NSF Grant No. GJ454.     

Rule-based languages

The paper presents a survey of the main formal rule-based languages and semantics. Both procedural (fixpoint) and declarative (model-theoretic) semantics are defined and discussed, including inflationary and noninflationary fixpoint semantics, and the semi-positive, stratified and well-founded semantics. The relative expressive power and com-plexity of the various languages are provided. Nondeterministic rule-based languages are also discussed, and it is shown how nondeterminism can circumvent some difficulties concerning the expressive power of the deterministic languages. Finally, languages with value invention (in the spirit of object-creation in oodbs) are presented and issues of expressive power specific to such languages are discussed.     

Relations of flow languages to Petri net languages

A.C. Shaw has introduced the concept of the flow expression which is an extended regular expression and state several results with some conjectures. His conjecture that the flow expressions define context-sensitive languages has been answered negatively by two of the present authors, that is, the flow languages are recursively enumerable.In this paper, it is shown that flow languages for some restricted class of flow expressions are equivalent to Petri net languages. Some related decision problems for flow expressions are also discussed.     

EOL languages are not codings of FPOL languages

One of the useful results concerning EOL languages states that a language is an EOL language if and only if it is a cording of OL language. In this paper we retine this result by demonstrating that there exist EOL languages that are not codings of languages that are generated by propagating OL systems with finite axiom sets. This solves Problem 10 from the L Systems Problem Book '75.     

Regular patterns, regular languages and context-free languages

In this paper we consider two questions. First we consider whether every pattern language which is regular can be generated by a regular pattern. We show that this is indeed the case for extended (erasing) pattern languages if alphabet size is at least four. In all other cases, we show that there are patterns generating a regular language which cannot be generated by a regular pattern. Next we consider whether there are pattern languages which are context-free but not regular. We show that, for alphabet size 2 and 3, there are both erasing and non-erasing pattern languages which are context-free but not regular. On the other hand, for alphabet size at least 4, every erasing pattern language which is context-free is also regular. It is open at present whether there exist non-erasing pattern languages which are context-free but not regular for alphabet size at least 4.     

Weakly context-sensitive languages as model for programming languages

Summary An abstract family of formal languages containing context-free languages and properly contained in (deterministic) context-sensitive languages is introduced. This family is comprehensive enough to contain e.g. Algol 60 without admitting too complex recursive constructions possible in the frame of general context-sensitive languages.This family is essentially a family of property-languages, whereby the considered properties are restricted to properties which are constructively definable from a finite number of context-free sets.     

Well-structured languages

This paper introduces the notion of well-structured language. A well-structured language can be defined by a labelled well-structured transition system, equipped with an upward-closed set of accepting states. That peculiar class of transition systems has been extensively studied in the field of computer-aided verification, where it has direct an important applications. Petri nets, and their monotonic extensions (like Petri nets with non-blocking arcs or Petri nets with transfer arcs), for instance, are special subclasses of well-structured transition systems. We show that the class of well-structured languages enjoy several important closure properties. We propose several pumping lemmata that are applicable respectively to the whole class of well-structured languages and to the classes of languages recognized by Petri nets or Petri nets with non-blocking arcs. These pumping lemmata allow us to characterize the limits in the expressiveness of these classes of language. Furthermore, we exploit the pumping lemmata to strictly separate the expressive power of Petri nets, Petri nets with non-blocking arcs and Petri nets with transfer arcs.     

Hybrid languages

Hybrid languages have both modal and first-order characteristics: a Kripke semantics, and explicit variable binding apparatus. This paper motivates the development of hybrid languages, sketches their history, and examines the expressive power of three hybrid binders. We show that all three binders give rise to languages strictly weaker than the corresponding first-order language, that full first-order expressivity can be gained by adding the universal modality, and that all three binders can force the existence of infinite models and have undecidable satisfiability problems.     

Insertion languages

The operations of insertion ( ← ) and iterated insertion ( ←₁ ) are simple variants of Kleene's operations · and 1 [15] in a manner similar to the operations shuffle and iterated shuffle (see e.g. [13, 23, 20, 14]). Using the operation of iterated insertion, we can generate both the semi-Dyck and the two-sided Dyck languages from certain finite subsets of these languages. Thus the class of languages of the form $\text{S}{}^{\mathrm{\leftarrow }}{}^1$ for finite S forms a natural class of generalized Dyck languages. This class is equivalent to the class of pure unitary languages discussed in [6]. We investigate this class further, by examining for it the problems of equivalence, ambiguity, and determinism, all of which are easily decidable. On the other hand, we show that the problem “$\text{S}{}^{\mathrm{\leftarrow }}\text{1 ∩ T}{}^{\mathrm{\leftarrow }}\text{1 = {λ}?}$” is undecidable for finite, unambiguous S and T. Furthermore, by extending the regular expressions to include the operations ← and $\text{←}{}_1$, we obtain the class of insertion languages which generalizes both the regular languages and the Dyck languages, but is properly contained within the class of context-free languages. Our main result here is that the problem “$\text{L = ∑}{}^1\text{?}$” is undecidable for the class of insertion languages. From this result, it follows that the equivalence problem and the problem “IsL regular?” are also undecidable for this class.     

Plex languages

The phrase-structure grammar scheme used for specifying string languages is extended to structures called plexes composed of symbols with an arbitrary number of “attaching points.” Classes of plex languages that parallel existing classes of string languages are defined, and these classes are shown to be distinct. Context-free grammars for languages of chemical structures, logic diagrams, electrical circuits, and flowcharts are given. Plex languages are used to specify the interconnection of encoded geometric curves to form mesh-like line patterns, and methods are given by which languages of such line patterns can be classified.     

Left-noncounting languages

LetX be a finite alphabet and letX ^* be the free monoid generated byX. A languageA X ^* is called left-noncounting if there existsk 0 such that forx,y X ^*,x ^k y A if and only ifx ^k+i y A. The class of all left-noncounting languages overX forms a Boolean algebra which generally contains properly the class of all noncounting languages overX and is properly contained in the class of all power-separating languages overX. In this paper, we discuss some relations among these three classes of languages and we characterize the automata accepting the left-noncounting languages and the syn tactic monoids of the left-noncounting languages.This research has been supported by Grant A7877 of the National Research Council of Canada.     

On the intersection of regex languages with regular languages

In this paper we revisit the semantics of extended regular expressions (regex), defined succinctly in the 90s [A.V. Aho, Algorithms for finding patterns in strings, in: Jan van Leeuwen (Ed.), Handbook of Theoretical Computer Science, in: Algorithms and Complexity, vol. A, Elsevier and MIT Press, 1990, pp. 255–300] and rigorously in 2003 by Câmpeanu, Salomaa and Yu [C. Câmpeanu, K. Salomaa, S. Yu, A formal study of practical regular expressions, IJFCS 14 (6) (2003) 1007–1018], when the authors reported an open problem, namely whether regex languages are closed under the intersection with regular languages. We give a positive answer; and for doing so, we propose a new class of machines — regex automata systems (RAS) — which are equivalent to regex. Among others, these machines provide a consistent and convenient method of implementing regex in practice. We also prove, as a consequence of this closure property, that several languages, such as the mirror language, the language of palindromes, and the language of balanced words are not regex languages.     

An algebraic approach to data languages and timed languages

Algebra offers an elegant and powerful approach to understand regular languages and finite automata. Such framework has been notoriously lacking for timed languages and timed automata. We introduce the notion of monoid recognizability for data languages, which includes timed languages as special case, in a way that respects the spirit of the classical situation. We study closure properties and hierarchies in this model and prove that emptiness is decidable under natural hypotheses. Our class of recognizable languages properly includes many families of deterministic timed languages that have been proposed until now, and the same holds for non-deterministic versions.